A CLASSIFICATION OF TREES AND APPLICATIONS OF TOPOLOGY AND GRAPH THEORY TO NEUROSURGERY By TAE-IL YI .sf^'^MTw^-.^f , -, '. f A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA 2000 ■ ■" .^ t-^^ ? HH"''--^* iX ^ , , V- Copyright 2000 by TAE-IL YI ■I r'> TO My parents, Beom-Young Sz Bong-Wol, who show me how to love, My wife, Moon-Sil, who shows me what is love, and My children, David & Peter, who are the reasons why I love ACKNOWLEDGEMENTS I would like to express my sincere appreciation to the members of my supervi- sory committee, Dr. Beverly Brechner, Dr. Philip Boyland, Dr. James Keesling, Dr. Li-Chien Shen, and Dr. Mary Kantowski, for their patience, knowledge, concern, and especially for showing me how to study and teach. I would especially like to thank my advisor, Dr. Beverly Brechner, who accepted me and gave me a chance to work with her. I also want to express my appreciation for all her effort and all that she has done for me, not only in my major field, but also in my life. I would like to thank Matthew Harvey who brought me some wonderful ideas and wrote the Mathematica programs. I would like to thank Dr. Francis Bova who brought me these questions which were 'new world' to me. 1 would like to thank Dr. Meeks for helpful conver- sations, and Dr. Thomas Wagner who gave me the information about neurosurgery that I did not know before. I would like to thank Dr. Yunmei Chen who gave me inspiration. I would like to thank Dr. Miklos Bona who showed me some insights of combinatorics. Finally, I would like to thank the Department of Mathematics that allowed me to be here and meet all these wonderful people. IV TABLE OF CONTENTS ACKNOWLEDGEMENTS iv ABSTRACT vii CHAPTERS 1 INTRODUCTION 1 2 AN AUTOMATED SPHERE PACKING PLAN FOR BRAIN TUMORS 5 2.1 Introduction 5 2.2 Linac 5 2.3 Procedure of Radiosurgery 6 2.4 Making a Sphere by Arcs of Beams 10 2.5 Sphere Packing Plan 10 2.6 ShelHng Algorithm 15 3 A CLASSIFICATION OF UNLABELED TREES 25 3.1 Introduction 25 3.2 Definitions 26 3.3 Vertex Sequence 28 3.4 Degree Sequence 36 3.5 Perfect Sequence and Main Theorem 44 3.6 Obtaining Perfect Sequences 45 3.7 Extended Partitions and the Algorithm 53 4 TREES AS INVARIANTS FOR BRAIN TUMOR SHAPES 59 4.1 Introduction 59 4.2 Definitions and Some Properties 60 4.3 Graphs for Sphere Packing Plans 64 4.4 Order in the Vertex Set 65 4.5 Maximal Tree from a Graph 71 4.6 Graph from a Maximal Tree 81 4.7 Algorithm for Our Maximal Tree 81 APPENDICES A SHELLING PROGRAM FOR SPHERE PACKING 82 A.l Program for Data Reading 82 A. 2 Program for Center Searching 83 B PROGRAM FOR THE MAXIMAL TREE OF A GRAPH 91 C PROGRAM FOR CLASSIFYING TREES BY SEQUENCES 93 C.l Program 93 C.2 Some Program Results 97 D LABELED GRAPHS AND TREES 102 D.l Number of Labeled Graphs and Labeled Trees 102 D.2 Sketch of the Construction of a Priifer-code 102 D.3 Reconstruction of a Tree from a Priifer-code 103 REFERENCES 105 BIOGRAPHICAL SKETCH 105 VI Abstract of Dissertation Presented to the Graduate School of the University of Florida in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy - •#■ ' A CLASSIFICATION OF TREES AND APPLICATIONS OF TOPOLOGY AND GRAPH THEORY TO NEUROSURGERY By Tae-Il Yi August 2000 Chairman: Dr. Beverly L. Brechner Major Department: Mathematics The work of this dissertation was motivated by our work with a medical group at the Brain Institute at the University of Florida. This group was led by Dr. Francis Bova, who raised the following questions: (1) Can you automate the time-consuming sphere packing process for our "multiple isocenters method of stereographic radiosurgery" for brain tumors? (This surgery is noninvasive, radiation surgery to destroy brain tumors.) (2) Can you classify the shapes of brain tumors? In this dissertation, we construct some algorithms and programs to (partially) answer these questions. Our major (joint) results are described below. Our first result is an algorithm and a program that produce a unique sphere packing plan for any given brain tumor shape, filling the shape with different size spheres in a unique way. This process automates the 'sphere packing' part of the vn surgery plan. Additional code by the medical group was necessary to allow for physi- cian input in certain critical cases. It was then possible for the medical group to incorporate this into their surgery plan, semi-automating it, and significantly reduc- ing the surgeons' surgery planning time. Our second result is a complete classification of unlabeled n-trees. We assign to each n-tree, a sequence of n nonnegative integers satisfying certain properties; and from each such sequence, we can recover the n-tree assigned to it. In fact, we present both an algorithm and code to produce not only the sequences, but also pictures of if. the corresponding trees. - . -^ • i Our final result is a first attempt at a topological classification of tumor shapes. We first use our sphere packing plan to construct a graph representing the tumor. We then have an algorithm and program which uniquely select a maximal tree in the graph. Thus we can assign a unique tree to each tumor shape. However, different graphs may produce the same tree. Our tree classification allows us to compare two tumor shapes very easily, by just looking at their corresponding sequences. In particular, different sequences come from different sphere packing plans, but the converse does not hold. Vlll CHAPTER 1 INTRODUCTION The work of this dissertation was motivated by two questions raised by Dr. Francis Bova, of the Brain Institute, Shands Hospital, and the Department of Neuro- surgery, all at the University of Florida. It turns out the different-sounding questions are very much related and are tied together naturally in this thesis. In fact, our results for the second question depend upon our results for the first question. Dr. Bova led a medical group, which joined with our mathematics group, for a number of discussions over a two year period. This resulted, for us, in both a joint medical paper [11] and in this dissertation. We also want to reference the dissertation [10] of Thomas Wagner, Dr. Bova's medical physics student, who worked with us. We expect to have three mathematics publications from this dissertation-from Chapters 2, 3, and 4, respectively. The paper resulting from Chapter 2 will be joint with Professor Beverly Brechner, Professor Yunmei Chen, and Dr. Thomas Wagner. The papers resulting from Chapters 3 and 4 will be joint with Matthew Harvey, an undergraduate student working with Professor James Keesling on his honors thesis. Further, we anticipate an additional paper, to be joint with Yunmei Chen and her student. Dr. Stacey Chastain. This anticipated work will be an analysis of the tumor shapes of approximately 1000 interesting tumor radiation surgeries done by Bova and his colleagues at the University of Florida. Dr. Bova's questions were the following: 1. Is it possible to automate the medical group's "multiple isocenters method of stereographic radiosurgery" to destroy brain tumors? 2. Is it possible to classify brain tumor shapes? In this dissertation, we develop some algorithms and programs related to these questions. In stereographic radiosurgery, which is noninvasive surgery, radiation is de- Uvered by means of coUimators-cylindrical metal tubes, with cylindrical holes through them, through which the radiation flows. The goal of stereotactic radiosurgery for a brain tumor is to deliver the desired dosage to the target, and only the target. This is not possible in reality. So they do the next best thing, which is to deliver enough dosage to the target, to avoid as much normal tissue as possible, and to deliver as little radiation as possible to whatever normal tissue must be affected. There are two additional important criteria-dose homogeneity and dose conformality. That is, we do not want 'hot spots,' which have been experimentally determined to cause com- plications; and we do want rapid falloff of dose levels outside the actual tumor. One of several such radiation surgery methods is called the 'Multiple Isocenter Method.' This involves filling the tumor image with spheres of different sizes, until the image is best filled up. In this dissertation, we call such a plan, a 'Sphere Packing Treatment Plan.' In Chapter 2, we develop both an algorithm, which is called a 'shelling process' (or 'grassfire process' in medical terminology), and a C-R- program to identify the centers and sizes of spheres for this sphere packing treatment plan. For any given brain tumor, our program gives us a unique sphere packing plan. This sphere packing plan can be represented numerically as a list of parameters of the spheres, namely the centers and radii of the spheres. Based on this algorithm, the medical group developed a proprietary program for an automated sphere packing treatment plan, including dosage distribution, and other things (see Wagner et al.[ll]). Since this program always produces the same plan for the same tumor, it can be used as a 'benchmark' against which to compare other treatment plans. In Chapter 3, we obtain a code to denote an unlabeled tree by a unique, ordered, nonnegative integer sequence satisfying certain properties. We call such sequences, perfect sequences. That is, we obtain a complete classification of unlabeled n-trees by means of the perfect sequences of n nonnegative integers. Thus we have our main theorem of this chapter, the Tree Classification Theorem, (Theorem 3.5.5): For any positive integer n, let Tin) be the set of unlabeled n-trees and V{n) the set of perfect sequences of n-trees. Then there is a one-to-one correspondence between T{n) and V{n). We show how to assign a perfect sequence to a given tree, and conversely, how to reconstruct a tree from a given perfect sequence. We also include an algorithm and a Mathematica program to produce not only all the perfect n-sequences, for any given positive integer n > 3, but also pictures of the corresponding trees. By means of this program, we get our classification of unlabeled n-trees and also the total number of n-trees. In Chapter 4, we make a first attempt at a topological shape classification of tumors-actually of the sphere packing plan associated with the tumor shape. We first assign to each tumor a unique graph, and from that, we determine a unique tree. We obtain the graph by assigning a vertex for each sphere, and an edge between each pair of vertices representing adjacent spheres. This produces a unique connected graph corresponding to each sphere packing plan. Then, by using the notion of cutvertex, we give an order to the vertex set. We then use this order to build a unique maximal tree contained in the graph. Next, we develop an algorithm and a Mathematica program to assign a unique tree to each sphere packing plan. This program produces a list of edges of the tree, making it clear which edges are incident. Using our results of Chapter 3, we can now assign exactly one perfect sequence to each tumor. However, it may happen that more than one tumor shape (or graph) gives rise to the same tree, and therefore to the same perfect sequence. Thus, we do not yet have a real classification of tumor shapes. However, if two perfect sequences are distinct, then their corresponding trees, and therefore their respective correspond- ing graphs and sphere packing plans, are also distinct. Therefore we may consider their shapes to be distinct. Thus, we have our main result of Chapter 4, Theorem 4.5.6: The perfect sequences are invariants of the shapes of arbitrary brain tumors. That is, if two brain tumors are represented by distinct perfect sequences, then their corresponding trees are not isomorphic, and therefore their respective graphs and sphere packing plans are not isomorphic. Thus, we may consider their shapes to be distinct. We refer the reader to Douglas[l], Gross[3], and Harary[5] for graph theory. We also refer the reader to Hall [4], Riordan[7] and Stanley [9] for combinatorics. CHAPTER 2 AN AUTOMATED SPHERE PACKING PLAN FOR BRAIN TUMORS 2.1 Introduction The goal of stereotactic radiosurgery for a brain tumor is to deliver the desired dosage to the target, and only the target. This is not possible in reality. So they do the next best thing, which is to deliver enough dosage to the target, to avoid as much normal tissue as possible, and to deliver as little radiation as possible to whatever normal tissue must be affected. There are two additional important criteria-dose homogeneity and dose conformality. That is, we do not want 'hot spots,' which have been experimentally determined to cause complications; and we do want rapid falloff of dose levels outside the actual tumor. One of several such radiation surgery methods is called the 'Multiple Isocenter Method.' This involves filling the tumor image with spheres of different sizes, until the image is best filled up. This noninvasive method of surgery, namely by using radiation, relies on a piece of equipment called the Linear Accelerator (or simply, Linac). In this chapter, we show how to automate the construction of a sphere packing plan for the tumor image. Most of the information in this chapter about treatment of a brain tumor is taken from Friedman et al.[2]. See [2] for further reference. 2.2 Linac According to Friedman et al.[2], the linear accelerator is a complex machine capable of producing X-rays. A large amount of energy is generated by the power supply, which then powers the filament shown. This causes electrons to be emitted by the filament, which are in turn accelerated to higher energies using a (microwave) wave guide. The electrons are then changed in direction by the magnet so that they impact on a heavy metal alloy target. This results in X-ray production that can then be coUimated or shaped by both primary and secondary collimators within the linear accelerator head. This beam is further coUimated for radiosurgery by the tertiary radiosurgery collimator. (See Figure 2-1 and Figure 2-2.) The Linac is mounted on a rotating gantry such that the beam has a center of rotation about 1.5m above the floor. Usually, the isocenter accuracy is defined within a 2mm sphere. Because stereotactic radiosurgery depends on optimized accuracy, an improved system was designed at the University of Florida, by adding a set of bearings to the stereotactic collimator system and under the patient table. As a result, this new system achieves mechanical accuracy within 0.2mm±0.1mm for defining the treatment isocenter of beam delivery. The tertiary collimators are generally circular and allow improved centering of the treatment beam. The sizes of these collimators are from 5 to 40mm in 2- to 5-mm increments. 2.3 Procedure of Radiosurgery The procedure of radiosurgery is separated into 5 steps as follows. (1) Head ring attachment (2) CT scan (3) Image Processing (4) Planning (5) Treatment delivery For more detailed information, refer to Friedman et al.[2]. (1) Head ring attachment •; ^ -': ■ ,' > j ^ ^/^- -'5 j The stereotactic radiosurgery treatment requires attachment of a stereotactic head ring. This ring provides accurate information about the position and the shape Filament Waveguide Electron beam Power supply iH-iHI-f+l-H- (I^^M^£& mnnnmiBixumnrnmil^ Magnet ' Heavy alloy target Primary (Internal) collimators Rattening filter Secondary (Adjustable) collimators Tertiary (Radiosurgery) collimators Photon tieam tor radiosurgery Floor stand with treatntent arm atxjve "> ." Figure 2-1. System of Linac (Friedman et al.[2]) Figure 2-2. Operation of Linac (Friedman et al.[2]) of brain tumors from the computer tomography (CT). This ring also helps to insure that the treatment target is accurately placed at the precise isocenter of the Linac. (2) CT scan After attaching the head ring, a series of cut filming is taken. Eighty to 150 CT slices are taken per patient. For radiosurgical treatment planning, getting the accurate size and shape of the target is very important. Underestimation of the target size may result in treatment failure. Overestimation of size results in the inclusion of normal brain tissue within the treatment volume. Misrepresentation of an irregular target shape may lead to radiation damage of normal brain tissue. The accuracy of CT scanning depends on the size of the pixels that make up the scan image. The lateral and AP accuracy of scanning is approximately 0.6mm. But the axial dimension is determined by slice thickness of the CT scan, which is 1mm in general. The physicians use the so-called Brown-Roberts- Wells coordinates-or, simply BRW coordinates-which are called lateral (Lat), anterior-posterior (AP), and axial (Ax) coordinates. These are the x, y, and z coordinates, respectively. The direction of the lateral coordinate is from the left hand side ear to the right hand side ear of the patient. So the lateral view (or sagittal) is similar to the side view of the head, that is, views of shces along the lateral axis. This is the same as yz-plane views. The direction of the AP coordinate is from the back side of the head to the face. So the AP view (or coronal) is similar with the front view of the head, that is, views of slices along the AP axis. This is the same as xz-plane views. The direction of the axial (or vertical) coordinate is from the neck to the top of the head. So the axial view (or trans-axial) is similar to the sky view of the head, that is, views of slices along the axial axis. This is the same as xy-plane views. (See Figure 2-4.) (3) Image Processing An MRI scan has been done the day before surgery. Using a mouselike device, the CT and MRI images are transferred to the computer screen and fused. Then, 10 using geometric equations, the computer determines the lateral, AP, and vertical stereotactic coordinates of each point in each CT slice. (4) Planning Physicians use a mouse and their own judgment to 'eyeball' the location and the size of spheres for the treatment plan. (5) Treatment delivery The geometric sphere packing plan, developed as in (4), is combined with a proprietary dose planning program, and the resulting treatment plan is delivered by the Linac. 2.4 Making a Sphere by Arcs of Beams By varying the angle of the gantry and the angle of the table, one can deliver a radiation beam to the target from any angle within the range of the rotation. The shape of the common intersection of an arc of beams passing through one isocenter is a sphere. The neurosurgeons deliver a series of arcs (usually 5 or 9 arcs) to produce a single isocentered sphere shape. For an ellipsoidal target, they use fewer numbers of arcs to make a single isocentered ellipsoid shape. (See Figure 2-3, 2-4 and 2-5.) So, if the target shape is very close to a sphere or an ellipsoid, then the treatment plan is relatively easy compared to an irregularly shaped target. In that case, we need to create a geometric treatment plan. 2.5 Sphere Packing Plan As seen in the previous section, the physicians know how to irradiate-to- (eventually)destroy tumors which are shaped like spheres or ellipsoids. For a non- spherical shape of tumor, they try to fill the target with several spheres of different sizes. This is called the 'sphere packing' treatment plan. After finding a sphere packing plan, they treat each sphere separately as de- scribed in the previous section. So, multiple isocenter radiosurgery planning includes 11 Figure 2-3. One isocenter plan with five arcs of radiation (Wagner et al.[ll]) i 12 (270') (ago") (70') I H G FED C BA Figure 2-4. One isocenter plan with nine arcs of radiation (Friedman et al.[2]) 13 TARGET ^ ^ z> ^ ^ *N<^.. V \ ', V ' / ' // ,- » *V \\ \ > -^<^> \^^0.'' !/'/'/ '-''-' <^ B ^ -CJ, T? ,J> ;^ : , <3 "^ ^ . ^>~''->x\\ii^'.-/;.-;!^ ^>-;\\ /;'-^:5^ TARGET '''■■^'V^f^■^^;" '//■■'"•>■•'' Figure 2-5. Plan for a sphere shape and an ellipsoidal shape (Friedman et al.[2]) 14 the problem of determining the best sphere packing arrangement with which to fill the target volume. General methods for this treatment plan are iteratively based, dosimetrically driven algorithms. But these methods require many computations in order to compute a radiosurgical plan dose distribution, and then to evaluate the quality of the dose distribution. So geometrically based radiosurgery optimization has been suggested as a possible alternative means. However the method the physicians choose relies on human decisions and experience. Thus, for the same target, different surgeons may produce different plans. Even the same surgeon, doing the plan twice for the same target, may produce different plans. And the planning takes a long time, especially for a complicated target which needs more than 10 spheres. It might take as much as two hours of planning for a difficult case which needs about 20 spheres. During that time, the patient has to wait with the head ring attached to his or her head. And most importantly, even after spending the time to make a plan, many physicians without sufficient experience, are not sure if the plan is a 'good' one. Therefore, we provide an automated sphere packing method for the treatment plan (see Wagner et al.[ll]). This method shows potential to significantly aid the planning of difficult multiple isocenter cases. Based on tests with irregularly shaped phantom targets and with a representative sampling of clinical example cases, the method demonstrates the ability to generate radiosurgery plans comparable to, or of better quality than, multiple isocenter Linac radiosurgery plans found in other literature. At the same time, this program always produces the same treatment plan for the same tumor shape. So it can be used as a 'benchmark' to compare with other plans for the given tumor shape. Moreover, this program provides the treatment plan in a relatively short time. For a very difficult case which needed more than 18 spheres, this program took less than 3 minutes instead of more than the 1.5 hours ,15 which were needed when the physicians created the plan using traditional methods. The algorithm of this program is shown in Figure 2-6. In the following section, we explain the 'shelling algorithm' which we used in this program to get the centers and sizes of spheres for the sphere packing plan. 2.6 Shelling Algorithm The shelling procedure is best illustrated in Figure 2-7 to 2-16. The major steps of this shelling procedure are as follows. (1) Transferring the data of the boundary of the target From the CT scan, each point which is identified from the target contour data file can be mapped into a three dimensional array, since each CT scan shows the trans-axial view for a specific axial coordinate value. In the three dimensional array, we assign the lateral-, AP- and axial-coordinates to be x-, y- and z-axes, respectively. For each individual case, there are minimum and maximum values for x, y and z- axes. We assume the minimum value is always one. We get this information from the Program for Data Reading. (See Appendix A.l.) Let the target be minimally enclosed in an x-range beginning with one and ending with Mj,, a y-range beginning with one and ending with My, and a z-range beginning with one and ending with M^. Now we put 'safe bumper' layers sur- rounding the target. That is, we enlarge the box containing the target to ET = [0, M:, + l]x [0, My + l]x [0, M, + l]. ET stands for 'enlarged target box.' We assume that the dimension of each voxel is 1x1x1. Then we will number the voxels in a lexi- cographic manner, beginning with and ending with {Mj:+l)x{My + l)x{M^ + l) — l, giving us a total of (M^ -|- 1) x (M^ -|- 1) x (Mj -f 1) voxels with which we will work. Now we want to identify the voxels in ET in two different ways: first, by a set of coordinates {a, 6, c), and second, by an integer representing a counting procedure. Here, a is the left hand endpoint of the x-value of that voxel, b is the left hand Ui' '.. ?..,..- : w^-f rvLH ■« V 16 endpoint of the y- value of that voxel, and c is the left hand endpoint of the z- value of that voxel. The second notation for the voxel (a,6,c) is by some integer n. The voxels are counted, using a lexicographic ordering beginning with and ending with {M^ + 1) x {My + I) x (M^ + 1) - 1 which is denoted by nofdata in the program (see Appendix A. 2). Then the voxel denoted by {a,b,c) is numbered as c X (Mj; + 1) X {My + 1) + a X {My + 1) + b. And it is clear that, for every < i < nofdata, there are unique nonnegative integers, a,b,c, such that i = c X (M:, + 1) X (My + 1) + a X {My + I) + b. That is, for every < z < nofdata, one and only one voxel is assigned. Note that Figure 2-7 to Figure 2-14 show the same trans-axial view at different stages of the algorithm. Thus these figures show the data of a fixed axial-coordinate value. (2) Assign a status value for each voxel For every < i < nofdata, the status value for the i-th. voxel is denoted by cc[i]. That is, we denote the status value for the voxel with coordinates {a,b,c), by cc\i] where i = ex {M^ + I) x {My + I) + a x {My + I) + b. The following is the procedure to assign status values. First of all, let cc[i] = —3 for every < i < nofdata. Then we assign the number, —1, as the status value for each voxel corresponding to any of the target contour data. Next, for every < j < Mj, we assign cc[j x{M:, + l)x{My + l)] = 0, because the j x (M^ -h 1) x (My -h l)-th voxel is the voxel at the left lower corner for every j-th trans-axial view; that is, the voxel belongs to the healthy tissue. (See Figure 2-8.) For each voxel with cc[i] = —3, we define cc[i] = if any of cc[i — 1], cc[i + 1], cc[i — (My -I- 1)], cc[i -t- (My -h 1)] is 0. Note that this method produces zeros for every voxel in the safe bumper layers. (See Figure 2-9.) (3) Shelling the target voxels We proceed by mathematical induction on j, for '1 ' 0<J< X min{M^, My, M^} 17 For i = to {M^ + 1) X {My + 1) x (M, + 1) - 1, if the i-th voxel is assigned -1 or -3 for its status value, and if any of cc[i - 1], cc[i + 1], cc[i - {My + 1)], cc[i + {My + 1)], cc[i - {M, + 1) X {My + 1)], cc[i + {M, + 1) X {My + 1)] is equal to j, then we assign a new status value for the i-th voxel as c[i] = j + 1. Note that Figure 2-7 to Figure 2-14 show only a two-dimensional figure. But this procedure is held in a three-dimensional array. This process is repeated until the deepest lying voxels have been identified. The deepest lying voxel in the entire target volume would be the best location for an isocenter. And at the same time, the status value assigned to the deepest voxel indicates the radius of the sphere, which is one less than the status value of the voxel. This completes our induction. (See Figure 2-10.) (4) Removing the largest sphere At this moment, we might have several different voxels which have the same largest status value. So we choose the smallest numbered voxel as the center of the first largest sphere to be removed from the target. But in the program in Wagner et al.[ll], we choose the most effective voxel to be the center of the first largest sphere, by using the 'score function' which was developed by Tom Wagner. We think of the resulting sphere in the tumor as 'removed,' and therefore we can assign the new status value zero for these voxels in the sphere. To determine which voxels form the sphere that is removed, we do the following: Let R = voxel at the center of sphere to be removed. Let r = status value of R. Then we remove all voxels S with the property that distance(center of R, center of S) < r - 1. (See Figures 2-11 and 2-12.) Now, we proceed by mathematical induction on j, for < J < - X min{Mj;, My, MJ . For i = to (M^ -|- 1) x {My + I) x (M^ -|- 1) - 1, if the i-th voxel has status value > j, we reassign a new status value as follows: if any of cc[i — 1], cc[i + 1], cc[i — (My + 1)], cc[i + {My + l)], cc[i-{M^ + l)x{My + l)], cc[i + {M, + l)x{My + l)] is equal to j, then we assign a new status value for the i-th voxel as c[i] = j + 1. This 18 process is repeated until the deepest lying voxels have been identified. (See Figures 2-13 to 2-15.) And we repeat step (4) until we get either or 1 for the status value of each voxel in ET, the enlarged target box. Because the smallest size of the diameter of collimators is 5mm, we finish our program when the status values of all the voxels are zeros and/or ones. (See Figure 2-16.) The remaining part will be taken care of by the 'score function' (see Wagner et al.[ll]). After finishing this procedure, we have the spheres filling the target. In Figure 2-17, we see the sphere packing plan within a target by this method. For further detailed information about the score function and the automated sphere packing plan, we refer the reader to Wagner et al.[ll] and Wagner[10]. f START ' ' Build 3D voxel model of target Grassfire procedure (shelling) i L Reset non-coverec target voxels to "1" values i k — Yes — Evaluate score for maximum valued voxels Select voxel with maximum score as seed voxel Locate max score in neighborhood o) seed voxel Place sphere Figure 2-6. Sphere packing algorithm block diagram (Wagner et al.[ll]) 19 y 10 5 < • • • • • • • « • » < )• <•• » 4 • • « • • • • • • • « • • • • • • • • • • 9 • • • • • • • • • • • • • » • • » • • • • • • 5 10 15 20 -> X Figure 2-7. Transferring the data of the boundary of the target -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -1 -1 -1 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -1 -1 -1 -3 -3 -3 -3 -3 -1 -1 -1 -1 -1 -1 -3 -3 -3 -3 -3 -3 -3 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -3 -1 -1 -3 -3 -3 -3 -3 ■*■ -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -3 -3 -3 -3 ~1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -3 -3 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -3 -3 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -1 -3 -3 -3 -3 -1 -1 -1 -1 -3 -3 -3 -1 -1 -3 -3 -3 -3 -3 -3 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -1 -1 -3 -1 -1 -1 -1 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 Figure 2-8. Status values for the boundary and the initial voxel ■'■■■ ■' a ; .; ijv ,^*. > ,. • , :^. 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -3 -3 "3 -3 -3 -1 -1 -1 -1 -1 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -3 -1 -1 -1 1 "3 -3 -3 -3 -3 -3 -3 -3 -3 ~3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -3 -3 -3 -3 -3 "3 -3 -3 -3 "3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -1 -1 -1 -1 -1 -1 -1 -3 -3 -3 -1 -1 -3 -3 -3 -3 -3 -3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 Figure 2-9. Status values for the normal voxels 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 2 2 1 1 2 1 1 1 2 3 3 3 3 , 4 4 4 4 4 3 3 2 2 3 2 2 1 2 3 4 4 4 4 " fi 5 f) : i) 5 4 ; 4 3 3 4 3 2 1 2 3 4 i) : S 5 ^ i) 5 BSia i> ^ [j U 1 i) 4; ^1 2 1 2 3 4 4 5 i) :j ^ '1 : 4 ;> i) i) f) h o 4 4 3 2 1 1 2 3 3 4 4 4 3 3 4 4 4 4 4 4 3 3 2 1 2 1 2 2 2 3 3 3 2 2 3 3 3 3 3 3 2 2 1 1 1 1 1 2 2 2 1 1 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Figure 2-10. Sh lelli ng the r ■■■■ i. tai rgel , vo xels 21 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 1:2. 1 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 2 2 1 1 2 1 1 1 2 3 3 3 3 4 4 4 4 3 3 2 •A 3 2 2 1 2 3 4 4 4 4 5 5 5 5 5 4 4 3 3 4 3 2 1 2 3 4 5 5 5 6 5 5 6 6 .if •1 4 5 4 3 2 1 1 2 3 4 4 5 5 5 4 4 5 5 V^5 i i) 5 1 4 3 2 1 1 2 3 3 4 4 4 3 3 4 4 4 4 4 4 3 3 2 2 1 2 2 2 3 3 3 2 2 3 3 3 3 3 3 2 2 1 1 1 1 1 1 2 2 2 1 1 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Figure 2-11. Choosing the largest sphere 1 1 1 1 1 1 1 1 *2^ 1 1 1 1 1 1 1 2 2 2 1 1 2 1 1 1 2 3 3 2 2 3 2 2 1 2 3^ 4 3- 4 3 3 4 3 2 1 2 h ^4 4 f) 1 3 2 1 2 3 I r 1 4 3 2 1 1 2 4 4 4 4 3 3 2 2 1 2 3 3 3 3 2 2 1 1 1 1 1 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 Figure 2-12. Removing the largest sphere •,' * W- •'^X' 22 j ■ , ■ i 1 1 : ■ 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 2 2 2 3 2 2 1 2 2 3 3 4 3 2 1 1 1 2 3 4 4 3 2 1 2 2 3 4 4 4 3 2 1 2 2 3 4 3 3 2 2 1 2 3 3 2 2 1 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 2 2 1 1 1 1 Figure 2-13. Shelling the remaining target voxels 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 2 2 2 3 2 2 1 2 2 3 3 4 3 2 1 1 1 2 3 4 4 3 2 1 2 2 3 4 4 4 J. 2 1 2 2 3 4 3 3 2 2 1 2 3 3 2 2 1 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 2 2 1 1 1 1 Figure 2-14. Choosing the largest sphere of the remaining target 2 3 .i J i i ] ! ■ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 r 2 1 ■ T 2 2 1 2 1 1 1 1 1 2 1 1 1 2 1 2 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 Figure 2-15. Removing the second sphere 1 i J 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Figure 2-16. Removing all the spheres "' ,.5 24 patB.vol Figure 2-17. A sphere packing plan for a brain tumor (Wagner et al.[ll]) *w>- CHAPTER 3 A CLASSIFICATION OF UNLABELED TREES 3.1 Introduction In this chapter, we obtain a code to denote an unlabeled tree. By means of this code, we classify unlabeled n-trees. One may take an unlabeled n-tree to be the geometric realization of a connected, finite, simplicial complex without any simple closed curves. In particular, we call a tree an n-tree if and only if it is a tree with n vertices (that is, (n - 1) edges). Our code assigns a unique, ordered, 'perfect sequence', pf{T) = (c?i,o?2, • • • ,c^„) , to each unlabeled n-tree, T. And, conversely, given an ordered sequence of n integers satisfying certain properties, it is the perfect sequence of exactly one unlabeled n-tree. Thus, we have our main theorem, the Tree Classification Theorem (Theorem 3.5.5). We then show how to reconstruct the tree shape from a given perfect sequence, by hand. Our work includes an algorithm and a Mathematica program (see Appendix C.l) that produce a fist of all the perfect sequences for all possible n-trees, thus also producing the number of n-trees, for any given n. For some examples, see Appendix C.2. Since our algorithm and program are based upon our main theorem, we know that all possible unlabeled n-trees are produced by the program. Thus the program gives us, for each positive integer n, a complete list of all unlabeled n-trees. Given n > 0, with sufficient computer power and time, our program will list all the unlabeled n-trees, thus telling us how many unlabeled n-trees there are. However, we do not have a simple formula that tells us how many unlabeled n-trees there are. This remains an open problem. 25 26 The Literature contains work regarding the classification of labeled graphs and labeled trees. In Lovasz[6], the Priifer-code is used to determine the number of labeled n-trees (see the Appendix D.2 and D.3). In Sloane[8], Sloane shows a table for n < 26. However, Sloane references Harary for the method he uses. In Harary[5], there is a simple formula for the total number of labeled graphs with n vertices (see the Appendix D.l). There is also a formula for the total number of unlabeled n-trees, but it requires knowing the number of roo^et/ n-trees, which is calculated inductively. And, even though Harary[5] contains n-tree shapes up to n = 10, there is no explanation of how to get the shapes of these trees, while our work does show how to get these tree shapes from our code. This chapter is organized as follows: Section!: Introduction Section 2: Definitions Section 3: Vertex Sequence Section 4: Degree Sequence Section 5: Perfect Sequence and Main Theorem Section 6: Obtaining Perfect Sequences Section 7: Extended Partition and the Algorithm ' 3.2 Definitions Most of the necessary definitions in this section are from Harary [5]. We refer the reader to Harary [5] for easy reference. Definition 3.2.1 A graph G = {V{G), E{G)) consists of a vertex set V[G) = {fi,. . .,u„} and an edge set E{G) = {ei,. ..,6™} C {{u,v}\u,v e V{G)} in which each edge is an unordered pair of two distinct vertices u and u, and the edge {u,u} is said to join u and v. For an edge {u,v} we say that u and v are adjacent vertices and the vertex u and the edge {u, v} are incident with each other, as are * .« ' -A r J - ' 'Jt 27 V and {u,v}. From now on, \V{G)\ denotes the number of vertices and \E{G)\ denotes the number of edges. For a vertex u € V{G), the vertex set A{u) = {v E G\v is an adjacent vertex of u} is called the adjacent set of u. Note that u ^ A{u). Definition 3.2.2 A walk is an alternating sequence (uo, ei,Ui, 62, . . . ,6^, Ufc) of vertices and edges s.t. t;,_i 7^ u, for i = 1,2, ...,A;, and e,- = {vi-i,Vi} for i = 1, 2, . . . , fc. If there is no confusion, a walk can be denoted by a sequence of vertices only in the path Hke (^1,^2, ...,Vk). A cycle is a walk (uq, Ci, Ui, 62, . . • , e/t, Vk) with k > 3 in which Vq = Vk is the only vertex repeated. A path is a walk with no repeated vertex. A {u,v)-path is a path with the first vertex u and the last vertex V. The length of the (u,u)-path, l{u,v), in a graph is the number of edges in the (u,u)-path. The distance d{u,v) between two vertices u and v is the length of a shortest path joining them, if any; otherwise d{u,v) = 00. Note that d{u,u) = 0. A graph G is connected iff every pair of vertices are joined by a path. A graph having no cycle is acyclic. Note that an acyclic graph can be disconnected. A forest is an acyclic graph. A tree is a connected acyclic graph. An n-tree is a tree with n vertices. Definition 3.2.3 We say that a graph G is isomorphic to a graph H if and only if there exists a bijection / : V{G) -)■ V{H) such that {u,v} € E{G) if and only if {f{u)J{v)} e E{H). Definition 3.2.4 An unlabeled tree is an isomorphism class of trees. We are interested in the total number of unlabeled n-trees and their shapes. For example, T^ = ({1,2, 3}, {{1, 2}, {2,3}}) and n = ({1,2,3}, {{2, 1}, {1,3}}) are different trees, but there is an isomorphism / : V{Ti) -^ ^(^2) by /(I) = 2, /(2) = 1, /(3) = 3. Thus they are the same unlabeled tree, so we want to count them as one unlabeled 3-tree. From now on, a tree implies an unlabeled tree unless otherwise specified. 28 Definition 3.2.5 The degree of a vertex u, defined by d{v), is the sum of the number of edges incident with v. A vertex v is called an endvertex if d{v) = 1. We will use the geometric, that is, topological realization of a graph inter- changeably with 'graph' as defined above. Proposition 3.2.6 [5] The following statements are equivalent for a graph T : (1) T is a tree. . ^ . (2) Every two vertices of T are joined by a unique path. (3) T is connected and \V[T)\ = \E{T)\ + 1. (4) T is acyclic and \V(T)\ = \E{T)\ + 1. Note that there are exactly n vertices and n-1 edges in an n-tree. Proposition 3.2.7 (Degree sum formula) [5] // G is a graph with the vertex degrees (/i,...,(/„, then Y^y^v(G)'^i = '^\^i^)\- Corollary 3.2.8 For an n-Tree T we have T^l, d{iH) = 2{n - 1) = 2\E{T)\ = 2{\V{T)\ - 1) where Vi is a vertex of T for i = 1,2, . . . ,n. Because a nontrivial tree satisfies Ylvev(T)^i'^) ~ 2|i^(T)| = 2(|V(T')| — 1), there are at least two vertices with degree 1. Thus we have the following theorem as a corollary. Theorem 3.2.9 [5] Every nontrivial tree has at least two endvertices. 3.3 Vertex Sequence In this section, we define the vertex sequence of a given n-tree. Definition 3.3.1 Let T = {V, E) be an n-tree. If d{v) = m, then there are m components of T — {v}. A branch of v (or simply a v-branch) is a subtree which is the closure of a component of T — {v}. We call the set of vertices in a u-branch a v-branch vertex set. If w 6 A{v), then the u-branch vertex set containing u is called the {v,u)-branch vertex set and denoted by B{v,u) (or B{u)). We call the 29 set B'{v,u) = B{v,u) - {v} the {v,u)-subbranch vertex set, which is denoted by B'{u) if there is no confusion. The subtree consisting of B'{v,u) as the vertex set and {{s,t} e B'{v,u) x B'{v,u)\ {s,t} G E{T)} as the edge set is called the {v,u)- subhranch. Example 3.3.2 Let T be the 10-tree shown below. ♦ « ♦ < * '^ w X y Figure 3-1 Since d{v) = 4, there are 4 components of T — {v}. Since A{v) = {r, i,u;,j/}, we have that B{v,r) = {t;,r,5,g,p}, B{v,t) = {v,t}, B{v,w) — {v,y;,u,.r}, B{v,y) = {v,y}, B'{v,r) = {r,s,q,p} B'{v,t)^{t} B'(v,w) = {w,u,x} B'{v,y) = {y}. On the other hand, we have that B{r,v) = {r,v,t,u,w,x,y}. That is, B{v, r) / B{r, v). And this is true for any tree except the 2-tree. In fact, for every n-tree with n > 2, there are at least 3 vertices, namely u,v, and w. Without loss of generality, let u and v be vertices adjacent to each other, and let the {w,v)- path contain the vertex u. Then w € B{v,u) and w B{u,v). Definition 3.3.3 A section of a sequence is a subsequence consisting of consecutive terms of the sequence. Definition 3.3.4 Let T = {V, E) be an n-tree with V = {x^Xi, . . . ,Xn}. We define the set, S, of sequences of the form s = (ui,f2) ■ ■ • ,^^n) , where 5 is a permutation of the Xi''s in V{T), to be those sequences satisfying: 30 (*) for any Vj with 1 < j < n, Uj+i € A{vk) - {ui, f2, • • • , Vj} where k = max{i G {l,2,...,i}| A{v,) - {vi,V2, . . . ,Vj} ^ 0}. Then S is called the vertex sequence set of T and each element, s, in S is called a vertex sequence of T. . Definition 3.3.5 For any u 6 V, we call Sy = {s e S\vi ^ v} C S the v-vertex sequence set. Definition 3.3.4 requires that the vertices in a sequence be listed in a particular way. The condition (*) ensures that all vertices are listed and that each is hsted exactly once. We can choose any vertex for the first term, Vi. Then the condition (*) says that, for the (i+l)-th term, we have to choose an unUsted adjacent vertex of Vi, if possible. If every adjacent vertex of u, is already used, then look backward along the sequence until we come to the first vertex which has an unused adjacent vertex. Then, for the (i+l)-th term, we assign one of the unused adjacent vertices of that vertex. To get a vertex sequence, we continue this procedure inductively. Note that every vertex sequence of an n-tree has n entries. Example 3.3.6 We show how to construct a vertex sequence of a given tree. Let T be the 7-tree shown below. t/ abode Figure 3-2 Since we have freedom to choose the first term, let vi = b. Then V2 G A{vi) — {vi} = A{b) — {6} = {a, c, /} — {6} = {a, c, /} = A{b) = A{vi). So V2 must be one of the elements of A{vi) = A{b) = {a,c,f}. Let V2 = c. Since v^ G ^(^2) — {^^1,^2} = A{c) — {b,c} = {b,d,g} — {6, c} = {d,g}, v^ must be either d or g. Let ^3 = g. Then V4 A{v3) - {ui,U2,U3}, since ^(^3) - {ui,U2,U3} = {c} - {b,c,g} = 0. On 31 the other hand, we have that ^(^2) - {vi,V2,V3} = {b,d,g} - {b,c,g} = {d} ^ 0. Therefore we have to choose d as U4. Then U5 = e since A{v^ — {^1,^2, ^3,^4} = {c, e} — {6, c,^, (/} = {e}. Since we have ^(us) - {ui,U2,^^3,^^4,U5} = {d} - {h,c,g,d,e\ =0, A(y^) - {vx,V2,V2„Vi,v^} = {c,e} -{6,0,5-, d,e} = 0^ A(U3) -{ui,U2,i^3,^^4,U5} = {c} -{6, c, (/,«?, e} =0, A{v2) - {vx,V2,V'i,v^,v^} = {h,g,d}- {h,c,g,d,e) =0, and Aiyx) - {vuV2, i'3, U4, ^^5} = {a, c, /} - {6, c, ^r, (/, e} = {a, /}, ^6 must be either a or /. Let v% — f. Then we have that A{ve) - {ui, U2, V3, W4, U5, ue} = {b} - {6, c, g, d, e, /} = 0, A{v5) - {vi,V2,vz,V4,V5,ve} = {d} - {b,c,g,d,e,f} =0, ^(^4) - {ui,U2,^'3,^^4,^^5,t^6} = {c,e} - {b,c,g,d,e,f} ^^, A{v2,) - {vi,V2,Vz,Vi,Vz,Ve] = {c} - {6, c, 5, c/, e, /} =0, A{v2) - {vi,V2,V2„Vi,Vz,v&] = {b,g,d} - {b,c,g,d,ej} =0, and A(ui) - {vi,V2,'y3,^^4,^^5,^^6} = {a,c,f}-{b,c,g,d,ej} = {a}. Therefore vr must be a; that is, we construct a vertex sequence {vi,V2,...,V7) = (6, c, ^r, (f, e, /, a) . For a given tree we will get different vertex sequences if we choose different vertices whenever we have two or more choices. But the sequence t = (6, c, d, e, /, a, g) cannot be a vertex sequence of T above. In fact, we have V5 = f. But we have that A{v4)- {vi,V2,V3,V4} = {d} - {b,c,d,e} =0, A{v3) - {ui, U2, V3, U4} = {c, e} - {6, c, d, e} = 0, A(t;2) - {^1,^2,^3,^4} = {b,d,g} - {b,c,d,e} = {g}, and A{vi) - {vi,V2,V3,V4} = {a,c,f}-{b,c,d,e} ={a,f}. That is, the sequence t has /, one of the elements of A{vi) — {vi,V2.,V3,V4}, for V5 instead of g which is an element of A{v2) — {^1,^2, i'3,i^4}- It is a contradiction to the maximality of k in the definition of vertex sequence. Proposition 3.3.7 Let (ui, ^2, • • • , ^n) be a vertex sequence of an n-tree T. For any Vj with j > 1 there is unique 1 < k < j such that Vj G A{vk) — {ui, V2, . . . ., Vj-i}. Proof First of all, for any j > 1, we have Vj ^ v^ for i = 1,2, . . . , j — 1 from the Definition 3.3.4. Assume that there is j > 1 such that {vj, Vj+u- ■ ■ , t'n} n {{UiZlA{Vi)) U {^1, ^2, . . . , t^,-i}) = 0. 32 Then, for any u G {uj,Uj+i, . . . , v„} and any w € [UJZlAivi)) U {ui, V2, • • • , Vj}, there is no (■u,u;)-path in T. That is, T is not connected. It is a contradiction to the connectedness of a tree. Therefore there is I < k < j such that Vj 6 A{vk) - {vi,V2,...,Vj-i}. If there are 1 < A;i < ^2 < j such that Vj e A{vki) - {vi,V2,...,Vj_i} and Uj € ^(ufcj - {vi, ^2, . . . ,Uj-i}, then the two edges, {vj^Vk^} and {fjjUfcj}, are elements of E{T). There is a path between Vk^ and Vk^ in the subtree {{vuV2, . . . ,Vj_i}, E'} where E' = {{u,v} E E{T)\u,v e {vuV2, ■ ■ ■ ,Vj.i}}. The tree T contains a cycle consisting of {vj,Vk^}, {vj^Vk^} and the (t;fci,t;fc2)-path. This contradicts the fact that a tree is acyclic. Therefore there is only one I < k < j such that Vj € A{vk) — {fi, ^2, • • • , ^j-i}- -L From the Definition 3.3.4 and the previous lemma we get the following corol- lary immediately. Corollary 3.3.8 Let {vi,V2,....,Vn) be a vertex sequence of an n-tree. Then (1) V2 € A{vi) . . ■■ (2) If d{vj) > 2 for any j = 2, 3, . . . , n — 1, then Vj^i G A{vj). (3) For any j = 2, 3, . . . , n — 1 if d{vj) — 1 and there is i < j such that d{vi) > 3 and d{vk) = 2 for every A: = i + l,i + 2, . . . , j — 1, then Uj+i G A[vi) and Uj+i A{vp), for every p= 1,2,..., i- I, i + I,... J. Proposition 3.3.9 Let {vi, V2, . . . , Vn) he a vertex sequence of an n-tree and A[vi) = {vi^,Vi^,. . . ,Ui„} with 1 < li < I2 < . . . < Im- Then {t;i,t;2,...,u„} = U™i5(ui,ui.). Proposition 3.3.10 Let s = {vi,V2, ■ . . ,Vn) he a vertex sequence of a given n-tree T. If d{vj) = m for some j > 1, then there exist m vertices, Vi,Vj^,Vj^,...,Vj^_^ such that A{vj) = {r;,-, v^^ ,Vj^,..., Vj^_^ } with i< j < ji < J2 < ■ ■ ■ < jm-i ■ Proof For any j > 1 there exists unique i < j such that {vi,Vj} G E{T) by Proposition 3.3.7; that is, Vi G A{vj). So, for any Vk G A{vj) — {uj, j < k. 33 Since d{vj) - m, there are m - 1 vertices, Uii,^i2? • • • ) ^im-n such that A{vj) = {ui, Uj, , t;j2 , . . . , Uj„_, } with i<3 <n<J2< ■■■< jm-i- -L Proposition 3.3.11 Let s = (ui,U2, . . . , u„) 6e a vertex sequence of a given n-tree T. Let d{vi) = m and A{vi) = {uij, Ui^, . . . , ui^} be the adjacent set of Ui, named so that 1 < li < I2 < . . . < Im- Then, for any z = 1, 2, . . . , m, the set of vertices in the subbranch, fi'(ui, Ui,), forms a section in s starting with Vi^. Proof Clearly, the section containing uij starts with uij = ^2- Let B'(i'i,ViJ = {uijjUij+i, . . . ,uii+mi}. Assume that there is a vertex u E: V{T) — B'{vi,Vi^) such that (ujjjUij+i,. . .,?;ij+j,u, . . .) is a section of J. Since u ^ B'{vi^vi^), A{vi^j^k) — B'(vi, uij = for any k = 0, 1, 2, ... ,j from the definition. Thus ^i-oA{vl^+k) — B'{vi,vi^) = ^. That is, U;[.^oA(i'ii+fc) D ^'(^1, ^^i,)- On the other hand, A{vi^+k) C B'{vl,Vl^) forevery A; = 0, 1,2, . . . , j. Thus we have that U^=oA(uii+fc) C 5'(fi,Uii). Therefore U^=o^(^ii+*:) = B'{vi,vi^). That is, j = mi. Hence B'{vi,viJ forms a section in s. Since B'{vi,vi^) is a subbranch of Ui, Uij+mj-i-i ^ ^(m) for any u e B'{vi,vi^). Thus Vl^+rnl+l € A(ui). That is, vi^+rn,+i = vi^. For any i = 1,2, ...,m — 1, let B'(vi,Vi-) form a section in s and Ui,^.m,+i = t^i.+i- By a simi- lar method, B'(vi,Vi^^^) forms a section in s and Ui,^.i+TOi+i+i = ^i,+2- -L The section formed by a subbranch i?'(?;i,ui,) is denoted by (B'(ui,UiJ). From the previous proposition, we have the following corollaries. Corollary 3.3.12 Let s = {vi,V2, . . . ,Vn) be a vertex sequence of a given n-tree T. Let d{vi) = m and A[vi) — {vi^^vi^, . . . ,vi^} be the adjacent set of vi, named so that 1 < Ij < I2 < ... < Im- The section {B'{vi,Vi,)) precedes the section (5'(?;i, fi,^j)) in s for i = 1,2, ...,m — 1, and there is no other vertex between these two sections. Corollary 3.3.13 Let {vi,V2, . . . .,Vn) be a vertex sequence of a given n-tree T. For any j > I with d{vj) = m. > 2 let A{vj) = {vi,Vj^,Vj^, . . . ,Vj^_^} where i < 34 j < ji < J2 < ■■■ < im-i- Then {B'{vj,Vj,)) = ^uj,, Vj, +i, . . . ,Uj,.^.,_i^ for any i = 1, 2, . . . , m — 1. In particular, we have that ji = j + I- Note that B{vj, v,^_, ) = {vj, Vj^_^ , Vj^_,+u • • • , "j,n-i } is the {vj,vj^_^ )-branch vertex set for some j^ > jm-i- Corollary 3.3.14 Let (t;i,t;2, . . • ,fn) be a vertex sequence of a given n-tree. If i < j with Vj e A{vi) and Vj ^ A{vk) for every k = i + l,i + 2, . . . ,j — 1, then Vp ^ A{vk) for every p > j and k = i + l,i-\-2,...,j — 1. For any given vertex sequence s = {vi.v^, . . . ,Vn) and any vertex Vj ^ ui, Vi belongs to a branch of Vj. We want to give a special name to this branch. Definition 3,3.15 Let s = (i'i,f2,- • • ,Un) be a vertex sequence of a given n-tree T. For any j > 1 the root branch of Vj in s is the branch of Vj containing Vi. Note that there is no root branch for Vi. . . Proposition 3.3.16 Let {vi,V2, . ■ ■ ,Vn) E S be the vertex sequence set of a given n-tree T. For any I < j < n, if Vj^i A{vj)^ then Vj is an end vertex. Proof If Vj^i A{vj) for some 1 < j < n, then Vj has a unique edge with a vertex, v,-, with i < j by Proposition 3.3.7. That is, d{vj) = 1. Therefore Vj is an end vertex. ± Proposition 3.3.17 Let {vi,V2, . . . ,Vn) E S be a vertex sequence set of a given n-tree T. For any 1 < j < n there is an integer jm such that {vi,V2,...,Vj}[j{Vj^,Vj„+U...,Vn} is the vertex set of the root branch of Vj. Proof Let I < j < n and d[vj) = m. Then, by Proposition 3.3.10, there exist m different vertices, u,-, Ujj, Uj^, • . ■ , Uj„_, such that A{vj) = {wiS^ji, Wj2? • • • '^im-il with i < j < ji < J2 < . . . < im-i- From Corollary 3.3.13, we have that 35 That is, the union of all the subbranches of Vj except the root branch is a section from Vj^ to Uj„_i. Therefore the set of vertices in the root branch is {vi,V2,. ■ ■ ,Vj}U Note that, if jm > n, then the root branch is {^1,^2? • • • , ^j}- Corollary 3.3.18 Let 5 = (ui, i;2, . . . , u„) € S* be the vertex sequence set of a given n-tree T. Let j ^ 1. Then d{vj) — 1, that is, Vj is an end vertex of T, if and only if the set of vertices of the root branch of Vj is V{T) = {vi,V2,. ■ ■ ■, u„}- Proposition 3.3.19 Let s = {vi,V2, . . ■ ,Vn) be a vertex sequence of a given n- tree T. For any vertex Vj with j > I the {vi,Vj)-path in T is a subsequence of {vuV2,...,Vj). Proof For any vertex Vj with j > I there is a unique vertex Vk^ with kp < j such that Vj G A{vkp). For the vertex Vk^ there is another unique vertex Vkj,_i with kp^i < kp such that Vk^ G ^(ufcp_i)- Then we will have that Vi is the unique adjacent vertex of a previous vertex Vki . Therefore the (ui, Vj)-path is a subsequence (ui,Ufc,,...,Ufcp_,,t;ip,Uj} of {vi,V2,...,Vj) . ± Proposition 3.3.20 For any two vertex sequences si and S2 in the v-vertex se- quence set Sy = {s ^ S\vi = v} the root branch vertex sets of a vertex x ^ Vi — v in si and in 62 are same. Proof Let s\ = (^1,^2, ■ ■ ■ iVn) and ^2 = (1/1,^2, • ■ • , ■"«) be two different vertex sequences of a given tree T with Vi = ui. Let x be an arbitrary vertex in T with x / vi. Then there are two integers k and / such that Vk = x — w/. Let A{x) = {xi,X2., ■ ■ ■ iXm-iiV}- Since T is a tree, there is a unique (i;i,a:)-path in T. Then one of the elements of A{x) is in the (i;i,a;)-path. Without loss of generality, let y be in the (ui, x)-path. From the proof of Proposition 3.3.17 we have that {u^S,'B'{x,Xp)) = {^^-,'B\vk,Xp)) = {vk+uVk+2,- ■ -iVk+r) and (U,"LYB'(a:,x,)) ={U';-,'B'{ui,Xp)) = {ui+i,Ul+2,---,Ul+r) 36 for some r. Therefore we have that {vi,V2,...,Vk}U {vk+r-\-U---,Vn} = {?<1 , U2, • • • , "/} U {u/+r+l , • • • , "„}. That is, the root branch vertex sets of x in i~i and in S2 are same. ± Example 3.3.21 Let T be an 8-tree as shown below. .V .w r s Figure 3-3 u Clearly, si = {q,r,s,t,u,w,v,p) , S2 = {q,p,r,s,w,t,u,v) e Sr ^ {s E S\vi = q}. Let {vi,V2,...,V8) = {q,r,s,t,u,w,v,p) and (ui,U2, • • • , Ws) = {q,p,r,s,w,t,u,v) . Then the root branch vertex set of s is {p,q,r,v}. That is, {p,q,r,v} - {q,r} U {u,^} = {vuV2} U {u7,U8} and {p,q,r,v} = {q,p,r} U {v} = {^1,^2,^3} U {ug}- Therefore the root branch vertex sets are same but the position might be different. On the other hand, d{w) = 1 and the unique adjacent vertex oi w — ve is 5 = ^3. Thus s — V3 [s in the root branch of w = Vq. Therefore the root branch vertex set of iv = vq is {vi,V2.,V3,Vi,V5,Ve} U {vr^Vg} = {^1,172, ••• ,^8} = {q,r,s,t,u,w,v,p}. That is, the root branch vertex set of an end vertex is V{T) itself. 3.4 Degree Sequence In this section, we define the degree sequence of a vertex sequence. Definition 3.4.1 Let S be the vertex sequence set of an n-tree T. For any ver- tex sequence s = {vi,V2,...,Vn) G S, we call Dg = {di,d2, ■ ■ ■ ,dn) the degree se- quence of s where di = d{vi) and di = d{vi) — 1 for i > 2. We call the set D = {Ds\s G S} the degree sequence set of S. And, for any vertex v £ V, we * , . , .• ,-■ f •H M5>eH. .37 call Dy = {Ds\s € Sy] C D the v-degree sequence set of Sy. For any section {B{vj,Vj,)) = {vj,Vj,,Vj,+i,---,Vj,^i-i) of s, formed by the (uj, v^J-branch vertex set B{vj,Vj,), we define Bd{vj,Vj,) = {c([j, ofj,,dj,+i, . . . ,cfj,^i_i} as the (yj,i^j,)- branch degree set where cffc = o?(ufc ) — 1 for k — j, j, , j, + 1 , ■ • • , Jt+i — 1 • And we define the {vj,VjJ-branch degree section by {Bd{vj,Vj^)) = (^dj,dj-,dj-+i, . . . ,c/j,_^i_i) which is denoted by {Bd{vj^)) if there is no confusion. In the same way as in Definition 3.3.1, we define {Bd'{vj,)) = {Bd'{v^,Vj,)) = (4,(/j.+i, . . . ,o?j.^,_i) . Example 3.4.2 Occasionally, it may happen that there are two or more vertex se- quences of a given tree with the same degree sequence. In the following example, there are several pairs of vertex sequences with the same degree sequences, respectively. p r s t ■■■ ? Figure 3-4 . 4 • Since there are 5 vertices in V(r), there are exactly 5! different sequences of vertices of T having length 5 and using each vertex only once. But only 16 of them satisfy the condition (*) in Definition 3.3.4. Therefore the vertex sequence set, 5, of the given tree, T, consists of the following sequences 5i = (p,r,q,5,i), S7 = {r,p,q,s,t), sh = {s,r,p,q,t) , S2 = {p,r,s,t,q), 58 = (r,jo,5,i,g), sU = {s,r,q,p,t) , 4 = (g,r,p,5,f), 59 = (r,9,p,s,^), s\s^ {s,t,r,p,q), 54 = {q,r,s,t,p), s\o = {r,q,s,t,p), s\e = {s,t,r,q,p) , 55 = {t,s,r,p,q), sn = {r,s,t,p,q), se = (i, s, r, q, p) , 5^2 = (r, 5, t, q, p) . Then the degree sequences of these vertex sequences are D,, =(1,2,0,1,0), D,, = (3,0,0,1,0), Dsi, =(2,2,0,0,0), D,; = (1,2,1,0,0), £>,-, = (3,0,1,0,0), D,i, =(2,2,0,0,0), D,3 = (1,2,0,1,0), /},-, = (3,0,0,1,0), Dsi, =(2,0,2,0,0), !>,-, = (1,2,1,0,0), £>„■„ = (3,0,1,0,0), D,,-, =(2,0,2,0,0), Z),-, = (1,1,2,0,0), Dsu =(3,1,0,0,0), Z),-, = (1,1,2,0,0), /),f, = (3,1,0,0,0). 38 Now we have that That is, for some different vertex sequences, the degree sequences might be same. And, if the degree sequences are same, then the trees denoted by these degree se- quences are isomorphic. Remark: The sum of the terms in any degree sequence of a given n-tree is the same, namely, n — 1 . It is 4 in the above example, and it is same as the number of edges in the tree. See Theorem 3.4.6 below. Since di = d{vi) and </, = d{vi) — 1 for i = 2, 3, . . . , n, we have the following proposition. Proposition 3.4.3 Let Ds — {di,d2, . ■ . idn) be a degree sequence of a vertex se- quence s of an n-tree T. Then < di < n — 1, and < di < n — 1 for f = 2, ...,n. Proposition 3.4.4 li dj ^ for any 1 < j < n, then Vj^i is an adjacent vertex of Vj. Proposition 3.4.5 Let s = {vi,V2, . . . , Vn) be a vertex sequence of an n-tree T and Ds = {di.,d2, . . . ,dn) the degree sequence of s. For any j E {1,2, . . . ,n — 1} with dj = m > 1, if the set {uj+i, VJ4.2, . . . , u^} is the collection of all the Vj-subbranches except the root subbranch, then k > j -\- m. Proof Since dj = m = d{vj) — 1, from Proposition 3.3.10, the vertex Vj has m subbranches besides the root subbranch. Thus there are at least m endvertices in the collection of those subbranches other than the root branch. Therefore at least m terms in {dj,dj+i,. ..,dk) are 0. Hence k > j + m. ± Theorem 3.4.6 (First Reduced Degree Sum Formula) For any degree sequence Ds = {di.,d2,...,dn) of a vertex sequence s ^ S of a given n-tree T we have ^27=1^' =n- I = \E\ and 39 Proof di is the degree of a vertex, and the remaining n — 1 terms are each one less than the degree of a vertex. By the degree sum formula (Proposition 3.2.7), it is true that "^"i-i d{vi) = 2\E\. So ELi di ^di+ Y,"=2 di = ^(^^i) + EL2 div,) - ^"^2 1 = {d{vl) + Zl2d{v^))-{n-l} = EUd{vi)-in-l) ^2\E\-{n-l) = 2(n-l)-(n-l) = n-l = \E\. Then we have that d.+EUid,--^) = ^1 + Er=2 ^- Er.2 1 = Er=i di - (n - 1) = (n-l)-(n-l) = 0. 1 Corollary 3.4.7 For any degree sequence, Dj = (cfi, c^2, •••,cfn) of a vertex sequence s E: S of a given n-tree T, we have di + Er=2, d.i^oidi - 1) = Er=2, d.=o 1- Proof From the first reduced degree sum formula we have that c^i + E?=2(^'~^) ~ 0- Then =^i + E?=2K-i) = ^1 + Er=2, d,i.oidi - 1) + Er=2, rf.=o('^' - 1) = ^1 + Er=2, d,^o('^^- - 1) + Er=2, ci.=o(-i) = (/l + Er=2, d,#o(''^' - 1) - E"=2, ci,=0 1- Thus we get the result. ± Note that di > for any i = 1, 2, . . . , n. So (i, — 1 < if and only if di = 0. Corollary 3.4.7 shows that, in a degree sequence D {di,d2,---,dn) , the total number of terms is the same as di + E"=2 (di — !)• Therefore there are exactly di + Er=2 d.M^di — 1) endvertices in the given tree. Because of this, we have the following proposition. Proposition 3.4.8 For any degree sequence Ds — {di,d2, ...idn) of a vertex se- quence s ^ S of a given n-tree T, we have ■ 40 for every 1 < q < n. Proof Assume that there is q < n such that di + X1L2(^! — 1) = 0. Since Dg = {di,d2,...,dn) is a degree sequence of a vertex sequence s £ S oi the given n-tree T, we have that v^+i G A{vp) for some p < q. Thus at least one of the endvertices counted by Vp is one of u,+i, v,+2, • ■ • i '^n- That is, in the section {di,d2, ■ ■ ■ ,dg) , we have at least one less terms than di + X^^_2 d,=,to(^' "" ^)i ^^^^ ^^' ^i + EU..^oK-i)-EL2,..=oi>i- Then =^i + EL2K-i) = di + EU .i^M^^ - 1) + EL2, ..=o('^^- - 1) = ^i + EU..^oW-i) + EU..=o(-i) = ^i + EU..^o(^»-i)-EU<i.=oi > 1- This is a contradiction. Therefore we have di + E!=2(^« "" 1) 7^ ^"^^ every 1 < q" < n. 1 Theorem 3.4.9 (Second Reduced Degree Sum Formula) Let T — (V, E) be an n-tree. Let Ds = {di,d2, ...,dn) be the degree sequence of a vertex sequence s E S of the given n-tree T. For any jk > 1, let B'{vji^) = {vj^,Vj^^i, ...,Vj^^^-l} be a {vj,Vj^)-subbranch vertex set. Then we have ^;.+Es:;;(^«-i) = o and for every jk < q < jk+i- Proof Let E{B\vj,)) = {{u,v] G E{T)\u,v E 5'(u,J}. Then rKJ = (5>,j,£;(5'K)))cr is also a tree, and {B'{vjJ) = (uj^, u^^^.!, . . . ,t;j^^,_i) is a vertex sequence of the tree T{vj^). Note that d{vj^) = dj^ + l in T. Since Vj ^ B'{vj^), the edge {vj.Vj^} is not in the edge set E{B'{vj^)). Thus we have that d{vj^) = dj^ in the subtree 41 T{vj^). Then the result comes from the first reduced degree sum formula (Theorem 3.4.6) and Proposition 3.4.8. 1 Corollary 3.4.10 Let s = (wi,U2, . . . , Un) be a vertex sequence of an n-tree T and Ds = {di,d2y. . .,dn) the degree sequence of s. For any dj > 0, if the subsequence {vj,Vj+i,. . . ,Vp) is the collection of all the Vj-branches except the root subbranch of Uj, then and ^. + EL+i(^«-i) = o for every j < q < p- Proof For j = 1, they are true by the first reduced degree sum formula (Theorem 3.4.6) and Proposition 3.4.8. Let j > 1 and Vj 6 A{vt) for some t < j. (i) If dj = 0, then d{vj) = 1, that is, Vj is an end vertex. Since j > 1, Vj ^ V\. Thus the root branch is the whole tree by Corollary 3.3.18. Therefore {vf) is the collection of all the Uj-branches except the root subbranch and dj + Y7i=j+i{^i ~^) — d, =0. (ii) If dj > 0, then the subsequence {vj, Uj+i, . . . ,Vp) which is the collection of all the f j-branches except the root subbranch, is the {vt, z;j)-subbranch, since Vj € A(vt). By the previous theorem, we get dj + X^^=j4.i(<^i — 1) = 0. Thus the collection of all the Uj-branches except the root subbranch of Vj is the (u^, t;j)-subbranch. Therefore, by the second reduced degree sum formula, we get dj + X1Lj+i(^' ~ 1) t^ ^^^ every j < q < p. ± Not all of the nonnegative integer sequences with n entries can be a vertex sequence of an n-tree. There is a condition to being a degree sequence of an n-tree. Definition 3.4.11 Let D = ((/i,(/2, . . . ,</„) be a nonnegative integer sequence. We say that D satisfies the degree sequence condition^ briefly DSC, if and only if it satisfies all of the following: 4 ■■'.'•:■: * •„ . i"- ;> V a 42 (a) di >0. ' (c) For any j < n with clj - m > 0, there are exactly m + 1 integers, j < ji - j + 1 <J2< ■■■<jm< Jm+i(= n + 1 if i = 1), such that ^..+E-i^:;;(^-l)= for A; = 1,2,..., m. (d) For any jk with dj^ = / > 0, there are exactly / + 1 integers, jk < jki - jk + \ < jk, < ...< jk, < jk^,+^^ = jk+i such that Theorem 3.4.12 Let D = {di,d2.,. . .^dn) be a nonnegative integer sequence. Then D is a degree sequence of a vertex sequence of an n-tree if and only if D satisfies DSC. Proof [=>] This follows from Proposition 3.4.3, Theorem 3.4.6 and Theorem 3.4.9. [<=] Let V = {vi,V2,. ■ .^Vn} be a set of n different vertices. Let D = {di,d2,. . ■ ,dn) be a nonnegative integer sequence satisfying the above conditions. Since di > and di > for any i = 2, 3, . . . , n, we can assign the degree of each vertex vi G V by d{vi) = di and d{vi) = di + 1 for ? = 2,3, . . . ,n. Let j <n and dj = m > 0. From (c), there are exactly m + 1 integers, j < ji < J2 < ■ ■ ■ < jm < jm+u such that ji = j + l, and dj^ + Eiljl+i(^i - 1) = for k = 1,2, ...,m. Now we assign an edge between Vj and Uj^ for A; = 1,2, . . . ,m. That is, Vj,^ G A{vj) for i = 1, 2, ...,m. (i) If dji^ = / > 0, we assign an edge between Vj^ and Vj,^ for p = 1, 2, . . . , / by (d). We do a similar procedure for each vertex, Vj, assigned to dj > 0. Therefore Vj^ G A{vj) and Uj^ G A.{vji^) for /c = 1, 2, . . . , m, j = 1, 2, . . . , /. (ii) If dj, = 0, then we do not assign any new edge for the vertex Vj,. But it is already joined to the vertex Vj by an edge. Let J = (ui, U2, . . . , Vn) ■ Then all the vertices in s are connected. Since each vertex Vi is assigned di new edges and Yll-i di = n — 1 from (b), we have n vertices and 43 n - 1 edges. Then the set of all the edges assigned above, together with the vertex set V, forms an n-tree by Proposition 3.2.6. -L Remark: The proof of Theorem 3.4.12 shows how to construct a tree that corre- spond to the given degree sequence satisfying DSC. Example 3.4.13 Let £> = (3,2, 3, 1, 0, 0,0, 1,0,2, 0,0,0) be a nonnegative integer sequence having 13 entries. Let V = {ui, U2, • • • , v„} be a set of n different vertices. ^9 s .U12 ► 1^13 Vs V7 vw ^1 V2 V3 V4 V5 • vn ve Figure 3-5 (a) Clearly, X^-^j di = 12 and di = 3 > 0. So we expect a 13-tree. (b) Since d{vi) = 3, there are 4 different integers, I<li=2<l2 = 10<l3 = 13 < I4 = 14, such that d2 + Etsl^' -1) = 2 + (2 + 0-1-1-1 + 0-1) = 0, dio + Y^lliiidi — l) = 2 + ( — 1 — 1) = 0, and 0^13 = 0. We assign edges between Vi and each of ^2,^101^13. (c) (i) Since V2 = 2, there 3 different integers, 2 < 3 < 8 < 10, such that c?3 + J2LM - 1) = 3 + (0 - 1 - 1 - 1) = 0, and 4 + (dg - 1) = 1 - 1 = 0. We assign edges between V2 and each of V3 and vg. (ii) Since Vw = 2, there are 3 different integers, 10 < 11 < 12 < 13, such that dii = and di2 = 0. We assign edges between fio and each of vn and fi2- (iii) Since U13 = 0, we do not assign any new edge for ^13. But the vertex i;i3 is connected to vi by an edge. 44 In a similar way, we get {v3,V4},{v3,ve},{v3,V7},{vs,V9}, and {v4,V5}. Let E be the collection of all the edges above, that is, E = {{^^1, t^2}, {Ul, Uio}, {Vl, U13}, {"2, V3}, {U2, Vs}, {Uio, ^^u}, {Vl0,Vi2},{v3,V4},{v3,Ve},{v3,V7},{Vs,Vs},{v4,Vn}}. Since the edge set E contains 12 elements, the set T = {V, E} is a 13-tree. 3.5 Perfect Sequence and Main Theorem In the previous section, we showed that, for a given n-tree T, there exist many vertex sequences depending on the starting vertex and choice among the adjacent vertices for each successive vertex. Therefore the degree sequence set D for the given tree T contains many different degree sequences which denote the same tree T. We need a way to choose one degree sequence representing the tree T. First of all we want to define an order on the set of all finite, nonnegative, integer sequences. Definition 3.5.1 For any two finite nonnegative integer sequences D = {pi,p2i ■■■■,Pk) and E = {qi-,q2, ■■■,qi) , D < E \i and only if either there is m < min{A;,/} such that pm < q-m and p,- = gi for all i = 1, 2, . . . , m — 1, or k < I and pi = qi for all i = 1, 2, . . . , A;. We write D < E \{ D < E ox D = E. Proposition 3.5.2 Let D be the set of all degree sequences of an n-tree. The degree sequence set, (jD, <), is a totally ordered finite set. Proof For any two different degree sequences the order defined above is well defined. Since each term di of a degree sequence is nonnegative and less than n and the length of each degree sequence is n, the degree sequence set D is a, finite set. Thus {D., <) is a totally ordered finite set. ± Definition 3.5.3 For a given n-tree T, let S be the vertex sequence set of T and D the degree sequence set of T. Then the maximum degree sequence in D is called the perfect sequence of the given tree T, and it is denoted by pf[T). For the perfect sequence, pf{T), of a given tree, T, there is a vertex sequence s = {vi,V2.,...,Vn) G 45 S such that the degree sequence of s is pf{T). We call s a perfect vertex sequence of the tree and Vi a perfect vertex of the tree. In the Example 3.4.2, the perfect sequence is (3, 1,0,0,0) and there are two different perfect vertex sequences, ^n = {r,s,t,p,q) and Su = {fiS,t,q,p) for it. But the trees represented by 5ii and 512 are isomorphic. For any given tree the perfect sequence is unique by Proposition 3.5.2. But there may exist several different perfect vertex sequences. If the given tree is a labeled tree, then these perfect vertex sequences denote different labeled trees. But these labeled trees are isomorphic to each other; that is, there is a unique unlabeled tree. Therefore, for a given perfect sequence, there exists a unique unlabeled tree. Theorem 3.5.4 Let dg be the perfect sequence of a tree T. If T' is any other tree whose perfect sequence is also dg, then T' is isomorphic to T. Proof If T has more than one vertex sequence with the same degree sequence, then these vertex sequences all produce the isomorphic trees, by using the construction in the proof of Theorem 3.4.12. J. Because of this theorem, we have our main theorem below. Theorem 3.5.5 (Tree Classification Theorem) For any positive integer n, let T[n) he the set of unlabeled n-trees and V{n) the set of perfect sequences of n-trees. Then there is a one-to-one correspondence between T{n) and V{n). 3.6 Obtaining Perfect Sequences By Theorem 3.5.5, if we can construct the set of perfect sequences of n-trees, V{n)^ without being given any tree shape, then we can classify all the n-trees by this set. And, in the same way as in Example 3.4.13, we can get the different tree shapes from the elements of V{n). Proposition 3.6.1 For the perfect vertex Vi of a perfect vertex sequence s = (f 1, V2, ..., Vn) , we have d{vi) > d{vi) for i = 2, 3, . . . , n. 46 Proof If there is some k G {2,3,...,n} such that d{vk) > d{vi), then D^ = {d{vi), . . .) < Ds' - {d{vk), . . .) for any vertex sequence s' - {vk, . . .) . This contra- dicts the maximality of Dg. 1. Proposition 3.6.2 // Ds = {di,d2, ...,dn) is the perfect sequence of a given n-tree T, then n — 1 > di > di > dn — for any i = 2,3, ..., n — 1. Proof Since T is an n-tree and Ds is the perfect sequence, we have n — l>di. For any vertex u G V{T) we have d{vi) > d{u) by Proposition 3.6.1. Since di = d{vi) and di = d{vi) — 1 for every 1 < i < n, we have di > di for 1 < i < n. Since dn must denote one of the end vertices, each of which has degree 1, we have dn = 0. Therefore we have di > c?„ = for every 1 < i < n — I. 1. Definition 3.6.3 Let D = {di,d2, ...,dn) be a degree sequence. Then we say that D satisfies the ordered subbranch condition, denoted OSbC, if and only if D satisfies the following condition for all j > 1 : If d{v,) = m -f- 1 > 2, and B'{vjJ, 5>,J, ..., B'{vjJ with j < ji < j2 < ... < j„i are the subbranches of the vertex Vj other than the root subbranch, then {Bd'{vj^)) > (Bd'ivj^^^)) for every A; = 1, 2, . . . ,m - 1. Recall that {Bd'{vj-)) is a section of the degree sequence D. (See Definition 3.3.3 and 3.4.1.) Remark : If j = 1, then there is no root branch of Vi; instead, there is one more subbranch, Bd'{vj^^^), such that j„ < jm+i and {B'{vj^)) > {Bd'{vj^_^J) . Theorem 3.6.4 Let D — {di,d2, . . . ,dn) be a nonnegative integer sequence. If D is the perfect sequence of an n-tree, then it satisfies the DSC and the OSbC. Proof It is clear from Theorem 3.4.12 and the maximality of D. ± Proposition 3.6.5 Let T be a tree and v a vertex with the largest degree in T. Then there is exactly one degree sequence Dy for T starting at v and satisfying both DSC and the OSbC. ' \/::' ■' : v ..; rV.. 47 By the above proposition, the converse of Theorem 3.6.4 is not true. The following example is a counterexample. Example 3.6.6 Let A = {dud2, . . . ,du) = (3,2,2,1,0,0,2,0,0,1,0,0). Then Sill ^» = 11 and di = 3 > 0. And the sequence A can be separated into 4 sections like (3), (2,2,1,0,0,2,0,0), (1,0), (0) . The second section can be sep- arated into 3 sections, (2), (2,1,0,0), (2,0,0), and the second and third sec- tion of these can be separated by (2), (1,0), (0) and (2), (0), (0), respec- tively. All of these subsections satisfy the second and third conditions of DSC. Thus the sequence A satisfies the DSC. That is, the sequence A is a degree se- quence of a vertex sequence {vi, ^2, . . . , f 12) of a 12-tree by Theorem 3.4.12. On the other hand, the sequence A satisfies the OSbC, since we have (2,2, 1,0,0,2,0,0) > (1,0) > (0) . But A is not the perfect sequence of the 12-tree. In fact, we rearrange the sequence A to get B = {dr + l,d2^di — l,dio,du,di2.,d3,d4,d5,de,d8.idQ) = (3,2,2,1,0,0,2,1,0,0,0,0). Note that d{vi) = di and d{v7) = d7 + l. Clearly the sequence B also satisfies the DSC and the OSbC. So B is also a degree sequence of another vertex sequence (^7, ^2, ^i, ^^10,^11? ^12) ^^3, ^4, ^5, V6,^^8, ^9) of the 12-tree. That is, A and B are degree sequences of the same 12-tree (see Figure 3-6). And we have B = (3, 2, 2, 1, 0, 0, 2, 1, 0, 0, 0, 0) > (3, 2, 2, 1, 0, 0, 2, 0, 0, 1, 0, 0) = A. Thus A is not the perfect sequence. Furthermore A cannot be the perfect sequence of any tree, because A and B denote isomorphic trees, and B > A. Vu t;io Vi t;i2 V2 Vr, V4 Vs Vq Figure 3-6 48 In this example we have that d{vi) = 3 = cfff?) which is the largest degree in the tree. That is, the perfect sequence must start with the largest degree. We will see in Example 3.6.8 that the degree sequence B is the perfect sequence of this tree. Note that (1,0) is the only possible degree sequence when c?i = 1. Therefore we assume di > I from now on. Now we show how to construct alternate degree sequences from A, similar to B. Assume that we have a nonnegative integer sequence A = {di,d2, ■ ■ ■ ,dn) satisfying the DSC and the OSbC. If there is 1 < i < n such that di < di, then A cannot be the perfect sequence of any tree by Proposition 3.6.2. So we assume that di > di for i = 2,3, ...,n, and there is at least one integer 1 < j < n such that dj = di — I. That is, there is an n-tree T = {V, E) such that A is a degree sequence of a vertex sequence s = (ui,U2, . . . , ?;„) of T, and T has at least two vertices of maximum degree di. Clearly, dj > 0. Thus Vj is not an end vertex in T. By Corollary 3.3.18, the set of the vertices of the root branch of Vj is not the set of vertices in A itself. So, from Proposition 3.3.17 there is j < m < n such that RB{vj) = {vi,V2.,. . . iVj} {J {vm+i,Vm+2, ■ ■ ■ i^n} is the set of the vertices of the root branch of Vj. Clearly, (uj+i,Uj+2, ■ • • , fm) is the section containing all of the subbranches of Vj except the root branch. Therefore, if dj = p, then there are p subsections of A Hke {Bd'{vj^)) > {Bd'{vj^)) > ... > (Bd'{vj^)) with j < ji < J2 < ■ ■ ■ < jp < m + 1, since A satisfies OSbC. On the other hand, let E{RB'{vj)) = {{u,v] e E{T)\u,v G RB'{vj)} be the set of edges in the root subbranchoi Vj. Then r = {RB\vj),E{RB'{vj))} is a subtree of T. Let S{T') be the vertex sequence set of T'. By Proposition 3.3.7, there is a unique integer 1 < A; < j such that Vk G A{vj). Clearly, Vk G RB'{vj). Let ^^^(r') be the t;fc-vertex sequence set of S{T'), in which the first term of each vertex sequence is Vk. Let Dy^{T') be the Vk-degree sequence set of Sy^{T') (see Definition 3.4.1). Since Dy^{T') is a finite set, there is a maximum sequence in Dy^{T'). We denote the maximum sequence in 49 Dy^{T') by mdR{vk). Note that di must be changed to di - \ in mdR{vk), since it is not going to be used for the first term anymore in the new degree sequence. Now we have that either mdR{vk) > {Bd'{vj^)) , or there is an integer I < q < V such that {Bd'{vj^)) > mdR{vk) > {Bd'{v^^^^)) . Note that mdR{vk) may be the smallest section, then Vj^_^^ would not exist. We rearrange the given degree sequence A to a new sequence in which dj + 1 is the first term and the subbranch degree sequences of Uj, mdR{vk), {Bd'{v,,)), (Bd'iv,,)), ..., {Bd'{vj^)) , are listed in descending order. Denote this new degree sequence by M^ . Since the subbranch degree sequences of Vj are listed in descending order in M^, the new degree sequence M^ satisfies the OSbC. Since M^ is a rearrangement of A with di = d{vj) = t/j + 1 > 0, di = d{vi) - I = di - 1 for some i > 1, and A satisfies the DSC, the new degree sequence M^ satisfies the conditions (a) and (b) of the definition of the DSC. Since mdR{vk) is the perfect sequence of T', it satisfies the conditions (c) and (d) of the definition of the DSC. Clearly, each section, {Bd'{vj,)) , satisfies the conditions (c) and (d) of the definition of the DSC. Therefore the new degree sequence M^ satisfies the DSC. Thus the new degree sequence M^. satisfies both the DSC and the OSbC. For the given nonnegative integer sequence A = (c/i, c?2, . . . ,c?n) > the set {M^\d{vj) = d{vi)} is a non-empty finite set, since A € {M^\d{vj) = d{vi)}. Therefore there is a maximum element in this set. Let Pa = max{M^\d{vj) = d{vi)}. Now A determines a unique tree T. Suppose B is another vertex sequence for T satisfying the DSC and the OSbC. Then {M^Jd{vg) = d{vi)} = {M„^|c/(uj) = d{vi)}, where Vq is an analogue of Vj, by Proposition 3.6.5. Therefore Pa is the perfect sequence fbr T. ' '. : * ^ / ^ ''A in By the above explanation together with Proposition 3.6.2 and Theorem 3.4.12, we have the following theorem. v '• "i -^ . ' ' t .<' 50 Theorem 3.6.7 Let A = {di,d2, . . . ., dn) be a nonnegative integer sequence satisfy- ing the DSC and the OSbC with di > d, for i = 2, 3, . . . , n. Then A = Pa if and only if A is the perfect sequence of an n-tree. In the following example, we show the degree sequence B in Example 3.6.6 is the perfect sequence of the tree. Example 3.6.8 In Example 3.6.6, A=(di,4,...,^i2) = (3,2,2,1,0,0,2,0,0,1,0,0) satisfies the DSC and the OSbC and d2 = d^, = dy — di — l. That is, d{v2) = d[v2,) — d{v7) = d{vi). Thus max{M^|_;' = 2,3,7} is the perfect sequence of the tree. For V7 we have that RB{v-r) = {t;i,U2, • • • , ^7} U {^10,^11,^12} and {Bd'{vs)) = (0) = {Bd'{vg)). Thus V = {RB'{v7),E{RB'{v7)} is the subtree produced by the root subbranch of vj. (See Figure 3-7.) Since vj G ^(172), we get the ^7- vertex sequence set Sy,{T') = { {v2,Vi,Vio,Vu,Vi2,V3,V4,V5,Ve) , (t;2, ui, U12, Uio, uii, U3, ^4, U5, ve) , {v2, ui, U12, uio, Vn,V3, Ve, V4, V5) , {v2,V3,V4,V5,Ve,Vi,Vio,Vu,Vi2) , (U2, ^^3, V4, U5, ^6, Ul, ^^12, ^^10, f u) , (1^2, t^3, ?^6, W4, V5, ^^1, t^lO, ?^11, ^^12) , {v2,V3,Ve,V4,V5,Vi,Vi2,Vw,Vu) }■ Then the Vr-degree sequence set of Sy^{T') is Dy,ir) ={ (2,2,1 (2,2,1 (2,2,0 (2,2,0 (2,2,1 (2,2,1 (2,2,0 (2,2,0 = { (2,2,1 (2,2,1 (2,2,0 (2,2,0 ,0,0,2,1 ,0,0), ,0,0,2,0 ,1,0), ,1,0,2,1 0,0), ,1,0,2,0 1,0), ,0,0,2,1 0,0), ,0,0,2,0 1,0), ,1,0,2,1 0,0), ,1,0,2,0 1,0)} ,0,0,2,1 0,0), ,0,0,2,0 1,0), ,1,0,2,1 0,0), ,1,0,2,0 1,0)} 51 Therefore we have the maximum sequence mdR{v7) in Dy^{T') as mdR{v'j) — (2,2,1,0,0,2,1,0,0). Since mdR{vr) = (2,2,1,0,0,2,1,0,0) > (0) = {Bd'{vs)) = {Bd'{v<,)), we have M^ = (3, 2, 2, 1,0,0, 2, 1, 0,0,0,0) . In the same way, we get M^ =(3,2,1,0,0,2,1,0,0,2,0,0) M4 =(3,2,2,1,0,0,2,0,0,1,0,0). Therefore niax{MyJj = 2,3,7} = My^. Since M4 =(3,2,2,1,0,0,2,1,0,0,0,0) > (3,2,2,1,0,0,2,0,0,1,0,0) = A, M^, which is B in the Example 3.6.6, is the perfect sequence of the tree. vn t?io Vi 1^12 V2 t>5 ^4 ^^3 ^^6 Figure 3-7 By the Tree Classification Theorem (Theorem 3.5.5) and the previous example, we have the following important corollary. Corollary 3.6.9 Let A = {d\^d2^. . . ^dn) be a nonnegative integer sequence satis- fying the DSC and the OSbC. If di — I > d^ for every i = 2, 3, . . . , n, then A is the perfect sequence for an n-tree. We will see in the following example how we construct a tree shape from a given maximal degree sequence. Example 3.6.10 Let D = ((/i,(/2, ..., c/io) = (3,2, 1, 2,0, 0, 1, 0,0,0) be a maximal degree sequence. Then we expect a 10-tree, T. Let i = (ui, V2, . . . , ^;io) be the vertex sequence having D as the degree sequence. Then d{vi) = di = 3, so the vertex Vi 52 has 3 edges. (See Figure 3-8.) Though there is no specific order for these edges, we label them as ei, 62, 63 for the convenience of explanation. 62 63 vi ei Figure 3-8 From the definition of vertex sequence (Definition 3.3.4) V2 is one of the elements of the adjacent set of vi, A{vi). Without loss of generality, let ei = {^1,^2}. Then ^2 has 2 'new' edges, 64 and 65, since c?2 = 2. Let 64 = {f2,y3}- By the same reasoning, V3 has 1 'new' edge, named cq. So cq = {t>3, V4}. Since (^4 = 2, V4 has 2 'new' edges, named 67 and es- (See Figure 3-9.) €2 e» 68 63 Vi Ci U2 64 ^3 ^6 1^4 67 Figure 3-9 Since c/5 = and (/e = 0, neither V5 nor Ue has a 'new' edge; that is, v^ and ve are end vertices. On the other hand, v^ and ve are the adjacent vertices of V4, since ((4 = 2. Thus vj is an adjacent vertex of one of {vi,V2iV3}. Since c?3 = 1 and V4 is the adjacent vertex of V3, V3 is not an adjacent vertex of vj. Since (^2 = 2 and we have only one adjacent vertex of U2, namely U3, we add an adjacent vertex, vr. (See Figure .3-10.) t?7 V6 62 65 68 ^3 Di ei ^2 64 U3 ^6 V4 er y^ Figure 3-10 53 Since dr = 1, vj has 1 'new' edge which connects with vs- Since ds = 0, there is no 'new' edge from vg. Since we covered up to d2, the remaining two vertices, vq and uio, are adjacent vertices of vi which has two 'unused' edges, 62 and 63. Let 62 = {vi,vq}, and 63 = {ui,i^io}- Since we are thinking about an unlabeled tree and we put the edge names for our convenience, there are no specific names for the vertices and edges. Thus we get the following 10-tree. (See Figure 3-11.) M w^ i( (vs) {V7) (ve) (wio) (vi) {V2) (vs) {V4) \0''i'';*^'' Figure 3-11 (^5) 3.7 Extended Partitions and the Algorithm In Definition 3.5.3 and the following explanation, it was shown that any tree can be represented by a unique perfect sequence. So, in this section, we develop an algorithm to produce all the perfect sequences for the n-trees for any positive integer n. From these perfect sequences, we get the shape of each n-tree as shown in the previous example, as well as the total number of n-trees. From Definition 3.4.1 and the First Reduced Degree Sum Formula (Theorem 3.4.6), we see that a degree sequence for an (n -|- l)-tree always has n-\-l nonnegative integers as entries and these integers always add up to n which is the number of the edges of the given (n + l)-tree. Thus, our first step in listing all possible degree sequences is to form ordered partitions of the integer n as sums of smaller positive integers. 54 Definition 3.7.1 An ordered partition of the positive integer n is a sequence of positive integers, (pi,P2, • • • ,Pm) , such that YllLi Pi = "• Note that I < m < n in the definition above. Definition 3.7.2 An extended partition of an ordered partition {pi,p2., . . . ,Pm) of the positive integer n is a sequence of n + 1 nonnegative integers, (c?i, (/2, • • • , dn+i) , such that {i)di=pi, X^"j"/ (fi = n, and . ; " (ii) there is a subsequence {dj^ ,dj^,..., dj^) such that dj^ = pk for A; = 1, . . . , m. Note that any entry di in the extended partition must be unless it is a member of the ordered partition. It is important that different extended partitions are produced not only by the different ordered partitions but can also be produced by the same ordered partition. For example, let ((ii,d2, . . . ,c?„+i) and (c?i, 6^2, . . . ,o('„^i) be two extended partitions of an ordered partition (pi,p2, • • • ,Pm) , and let {dj^,dj^, . . . ,dj^) and (rfjprfj^, • • • ,of(^) be subsequences, respectively, such that dj^ — di = pi = d[ and dj^ = Pk = d[^ for A; = 2, 3, . . . , m. Assume that ji ^ ti for at least one i. Then there are sections of zeros with different lengths between di,^ ,, and cf,- , and d'. and d'f^, respectively. So the extended partitions are different. Thus the order is very important in an extended partition. Also note that the length of the extended partition of n must be n + 1. So, for any given ordered partition, {pi,p2, ■ ■ ■,Pm) , we need to add n-m + l zeros to make an extended partition. Proposition 3.7.3 Let (c?i, c?2, • • ■ , c^n+i) be an extended partition of an ordered partition P = {dj^,dj^, . . . ,dj^) of the integer n. Then this extended partition sat- isfies the First Reduced Degree Sum Formula (Theorem 3.4.6). ■ f.' .: 'r '^T '■'...■'.■'- t^ y '^' '^--r ' ,' , i ■■ \ i % ' ■ . i J 55 Proof From the given extended partition ((/i, (^2, ■ ■ • , dn+i) of an ordered partition {dj^ , c^j2, . . . , dj^) of the integer n, we have that Xl"=i di = YlT=i ^h - " ^"^ ^1 + ES (^»- - 1) = ^1 + Er=2(^.. - 1) + ES! d.0F(^^- - 1) since d, + = d,, + Er=2(^.. - 1) + EK ..^p(^. - 1) = Er=i ^.. + Er=2(-i) + ES, ..^p(-i) = n + (m - 1)(-1) + (n - m + 1)(-1), :=n — m + 1— n + m— 1 = 0. ± Even though we have a very large number of extended partitions of n, some of them can not be a maximal degree sequence for an (n + l)-tree. So we first eliminate some ordered partitions that could not possibly result in maximal degree sequences. To do so, we need to check some properties of perfect sequences. Proposition 3.7.4 Let Ds = {di,d2,. . . idn+i) be the perfect sequence of a given (n + l)-tree T. If di ^ and di^i = 0, then = di^i = di^2 = ••• = <^»+di- Proof Since di^Q, the vertex Vi has di 'new' edges; that is, there are di adjacent vertices of u, and they are labeled by di consecutive integers after i. Since Dg is a perfect sequence, it satisfies the OSbC. That is, the vertex Uj+i is a vertex of the largest degree among the adjacent vertices of Vi. But di^i = 0. Therefore we have dj = for j = f + 2, i + 3, . . . , i + di. ± This proposition gives us a method to make an extended partition from an ordered partition by adding zeros. That is, we know certain extended partitions cannot be perfect sequences just by checking this property. Proposition 3.7.5 Let Dg — {di,d2, . . . ,dn+i) be the perfect sequence of a given (n + l)-tree T. If n > 2, then di > 2. Proof If di = 1, then di = for every i = 2,3, . . . ,n + 1 by Proposition 3.6.2. Since n > 2, there are at least 3 vertices in T. Thus we have that <^i + E"=2H^«~l) = 1 + E"=2 ("~1) ^ 1 + (~1 — 1) = — 1 / 0. This is a contradiction to the First Reduced Degree Sum Formula. Therefore di > 2. ± 56 According to the above proposition, the only trees whose perfect sequences start with or 1 are the tree with zero edge and the tree with one edge. The only degree sequence representation of a tree with zero edge is (0) , and the only degree sequence representation of a tree with one edge is (1,0). These are easy enough to visualize and count, so for the algorithm we work on the assumption that we are listing trees with at least two edges. Then the first term of the perfect sequence will be at least 2. The following proposition shows that we have an arc shape tree if the first term of the perfect sequence is 2. Proposition 3.7.6 If Ds = ((/i,(/2, • • • i^^n+i) is the perfect sequence of an {n-\-l)-tree T and di — 2, then di = 1 for i = 2, 3, . . . , n — 1 and dn = dn+i = 0. Proof By Proposition 3.6.2 we have that di € {0, 1} for any i = 2,3, . . . ,n + 1, since di = 2. Then the possible highest degree in T is degree 2. So T is just a linear tree with n edges. That is, there are exactly two end vertices which cannot be ^1. Therefore there are exactly two zeros in the sequence. Write a degree sequence for T, in the order of the vertices in the following figure. ^'n+l Vi V2 V3 Vn-1 Vn Figure 3-12 That is, start at a vertex adjacent to an end vertex and move in the longer direction first. Clearly the degree sequence resulting from this method contains the two zeros for Vn and Vn+i- Then we will get a degree sequence of the form D — (2, 1, 1, . . . , 1, 0, 0) . For the same tree, the numbers in a degree sequence cannot change, but only the order in which they occur can change by changing the position of zeros. And, clearly, the new ordered sequence < D. So the sequence D must be the perfect sequence of T. That Is, Ds = D. ± 57 Most of the extended partitions of n start with a 1 or a 2. Since the last two propositions classify trees whose degree sequences start with these values, we do not need to consider ordered partitions that start with 1 or 2. Proposition 3.7.6 shows that for any given number n of edges there is only one tree with n edges whose perfect sequence starts with a 2. In particular, it is a linear tree with n edges, since d^ = I for i = 2, 3, . . . , 7Z — 1. We add this sequence at the end of the algorithm. By Propostion 3.6.2, we do not need the ordered partitions in which the largest summand appears more than once or is not the first term in the ordered partition. If an ordered partition has either one or two entries only, then we can produce only one extended partition for each case. See the following Proposition 3.7.7 and Corollary 3.7.8. Proposition 3.7.7 Let Dg = {di,d2, ■ . ■ ,dn+i) be the perfect sequence of an {n + 1) - tree T with c?2 = 0. Then di = n and di = for all i > 1. Proof: Let J be a vertex sequence yielding a perfect sequence Dg of an (n + 1)- tree T. Since Dg is a perfect sequence and — d2 = d{v2) — l, all of the vertices in the tree other than Vi have degree 1, so all the terms in Dg other than di must be zero. By the First Reduced Degree Sum Formula (Theorem 3.4.6), we have di = n. L Corollary 3.7.8 If an ordered partition P = (pi,p2) "/ n has only two entries, then the produced extended partition, (c/i, (i2, . . . , c?n+i) , from P is such that di = Pi 5 <^2 = P2 and di = for i = 3, 4, . . . , n + 1. We demonstrated several necessary conditions which apply to a perfect se- quence of a tree. Unfortunately, while these conditions are sufficient in almost all cases, there are certain sequences which, although they satisfy all the conditions, are not perfect sequences of the trees they represent. The problems usually arise when the tree has two or more vertices of the largest degree. We saw a counterexample in Example 3.6.6. 58 Note that in the Example 3.6.6 the two degree sequences A and B have the same ordered partition, P = (3,2,2,1,2,1). That is, our algorithm produces the degree sequence B as one of the extended partitions of the ordered partition P. Therefore all we need to do is just drop the degree sequence A from the result of our algorithm. Each step described so far has involved checking each member of a list of possible degree sequences and removing those which could not be the perfect sequence of a tree. The last step is no exception. Given a degree sequence, we check if there is more than one vertex of maximal degree. If there are more than one (in Example 3.6.6, both vertices vi and vj — u\ have the same degree, 3), we write degree sequences for the tree starting at each such vertex. If the largest of these with respect to the ordering < is the sequence we are checking, then it is a perfect sequence. If some other vertex gives a larger degree sequence, it is false that the sequence we are checking is a perfect sequence. This is a surefire approach in that, given a degree sequence, it checks for a perfect sequence by considering every possible alternative for the maximum and seeing if the sequence in hand is the largest. CHAPTER 4 TREES AS INVARIANTS FOR BRAIN TUMOR SHAPES 4.1 Introduction A sphere packing treatment plan for a given brain tumor is produced in the first chapter. This plan can be represented numerically as a list of parameters of the dose spheres. In particular, the list consists of the coordinates of the dose center in millimeters along the lateral (Lat), anterior-posterior (AP), and axial (Ax) axes together with the radius of the dose sphere in millimeters. From these data, we can assign a unique corresponding graph by matching a sphere with a vertex and matching the adjacency of two spheres with an edge. Then, by using the notion of cutvertex, we give an order to the vertex set. We use this order to decide which edges to choose in order to obtain a unique maximal tree contained in the graph. Our main theorem of this section is Theorem 4.5.6: The perfect sequences are invariants of the shapes of arbitrary brain tumors. We then develop a Mathematica program (see Appendix B) to get a maximal tree of the graph for a sphere packing plan for a given brain tumor. In the near future, we plan to use this program to classify all the treatment plans which have been done at the Brain Institute of the University of Florida. We hope that the classification gives some insight about brain tumor shapes. In this chapter, we assume that a brain tumor is connected, so the graph representation for any brain tumor is a connected graph. 59 60 4.2 Definitions and Some Properties Definition 4.2.1 A graph G = {V{G),E[G)) consists of a vertex set V{G) = {vi, . . . ^Vn} and an edge set E{G) = {ei, . . . , e^} C {{u,v}\u,v G V{G)} in which each edge is an unordered pair of two distinct vertices u and v, and the edge {u,v} is said to join u and v. For an edge {u,v} we say that u and v are adjacent vertices and the vertex u and the edge {u,v} are incident with each other, as are V and {u,i;}. From now on, |V(G')| denotes the number of vertices and |i^(G')| denotes the number of edges. For a vertex u G V{G), the vertex set Ag{u) = {v G G\v is an adjacent vertex of u} is called the adjacent set of u in G. Since there is no loop represented by a single edge, in a graph in this article, no vertex is adjacent to itself. Definition 4.2.2 We say that a graph G is isomorphic to a graph H if and only if there exists a bijection / : V{G) -> V{H) such that {u, v} G E{G) if and only if {fiu),fiv)}eE{H). Definition 4.2.3 A walk is an alternating sequence (uq, ^i, ui, eg, . . . , e^, Vk) of ver- tices and edges s.t. t;,_i j^ Vi for i = 1, 2, . . . , A;, and Cj- = {vi^i,Vi} for every i. A cycle is a walk (uq, ei, fi, eg, . . . , ejt,Ufc) with k > 3 in which vq = Vk is the only vertex repeated. A path is a walk with no repeated vertex. A (u,v)-path is a path with the first vertex u and the last vertex v. A (u,u)-path\s di vertex u. The length of the (u,v)-path, l{u,v), is the number of edges in the (u,v)-path. So the length of (u,ii)-path is 0. The distance d{u,v) between two vertices u and v is the length of a shortest path joining them, if any; otherwise d{u, v) — oo. Note that a path of length > 1 is of linear shape. Definition 4.2.4 Let G = {V, E) be a graph where V = {ui,U2, . . . ,t;„}. Then, for any vertex v e V, we say that Pg{v) = j if and only if 61 j — m'm{i G {1,2, .. . ,n}| there is a {v,Vi)-pa,th. in G}. We call Pg{i^) the path-value, or simply the P-value of the vertex v in G. Definition 4.2.5 Let G = {V, E) be a graph. For any nonempth subset V C V, let F = { {u,v} e E \ u,v e V } C E. For any subset F' of F, the graph G' = (V, F') is called a subgraph of G. A graph G is connected if and only if every pair of vertices are joined by a path. A graph having no cycle is acyclic. Note that an acyclic graph can be disconnected. A forest is an acyclic graph. A tree is a connected acyclic graph. An n-tree is a tree with n vertices. Definition 4.2.6 The degree of a vertex v, denoted by d{v), is the sum of the number of edges incident with v. Definition 4.2.7 A cutvertex of a graph is a vertex of degree greater than 2, whose removal increases the number of components of the graph. Definition 4.2.8 A nonseparable graph is connected, nontrivial, and has no cutver- tex. A block of a graph is a maximal nonseparable subgraph. Thus if V is a cutvertex of a connected graph G, then G — v is disconnected. Note that the traditional definition of cutvertex (usually called cutpoint in graph theory) does not have the degree condition. But we do not want to separate any linear shape subgraph into several blocks because there is no difficulty in handling linear shape subgraphs in our algorithm. Thus we do not call a vertex with degree 2, a cutvertex in this chapter, even though it separates the graph. And if // is a block, then none of the vertices in H is a. cutvertex of H. Note that if there is no cutvertex in G, then the graph G itself is a block. This definition differs from the definition of block in Harary [5], because we have a different definition of cutvertex. Because of this, we have Proposition 4.2.10 below. Proposition 4.2.9 If a graph G is of linear shape, then the maximal tree of G is G itself. 62 Proposition 4.2.10 [5] Let v be a vertex of a connected graph G. The following statements are equivalent: (1) V separates G and d{v) > 2. (2) There exist vertices u and w distinct from v such that v is on every (u,u;)- path. (3) There exists a partition of the set of vertices V{G) — {v} into subsets U and W such that for any vertices u E U and w E W, the vertex v is on every {u,w)-path. Definition 4.2.11 Let G = {V, E} be a graph. For any vertex v e V we define the edge subset Ig{v) C E{G) by Ig{v) = {{v,u} e E{G)\ u € Ag{v)}. We call Ig{v) the incident edge set of v in G. Clearly, Ig{v) contains all the incident edges of the vertex v in G. Definition 4.2.12 Let G-{V,E} be a graph. For any subset F oi E we call the set V{F) = {v G. V{G)\ there is an edge e E F such that v and e are incident } the F vertex set. Proposition 4.2.13 [5] The following statements are equivalent for a graph T : (1) T is a tree. (2) Every two vertices of T are joined by a unique path. (3) T is connected and \V{T)\ = \E{T)\ + I. (4) T is acyclic and \V{T)\ = \E{T)\ + 1. Note that if a tree has n vertices, then there are exactly n — 1 edges. Definition 4.2.14 Let G = {V, E} be a connected graph and E' a subset of E. A connected subgraph T = {V, E'} is called a maximal tree of G if and only if T' = {V, E' U {e}} contains a cycle for any edge e E E — E'. Our work in this chapter produces a particular maximal tree for any given graph. So we have the following (well-known) theorem. Theorem 4.2.15 Every connected graph has a maximal tree. 63 Example 4.2.16 Let G be a graph with 14 vertices and 18 edges as in the figure 4-1 below. Figure 4-1 There are 3 cutvertices, 6, c, e. So the given graph G can be separated into 6 blocks as follows: Gi ={VuE,} = {{a,b}, {{a,b}}}, ■" ' G2 = {V2,E2} = { {b,c,k,l,m,n}, { {^c},{c,A;},{A;,/},{/,m},{m,n},{n,6},{6,A;},{A;,m} } }, G3 ={Vs,Es} = {{c,d,e}, {{c,d},{d,e}}}, G, ={V4,£4} = {{e,/,5}, {{e, /},{/, ^}, {5, e}}}, G5 ={V,,E,} = {{e,h,i}, {{e,h},{h,i}}}, and Ge ={Ve,Ee} = {{e,j}, { {e,j} } }. ■• •- a b h c c Gi Gi d Figure 4-2 64 4.3 Graphs for Sphere Packing Plans The sphere packing treatment plan S having n spheres for a given brain tu- mor, from Chapter 1, consists of the centers, cx,C2, . . . ,c„, and the radii, ri,r2, . . . ,r„, of the spheres with c, = (x,, y,, 2,) for every i, where x, is for the AP coordinate, y, is for the Lat coordinate and Zi is for the Ax coordinate of the center, c^. (Note that the physicians use diameters, rather than radii, in their data sets.) We consider the spheres to be the vertices of a graph, and we assign the vertex, Ui, for the sphere centered at Cj with radius r,. Now we can assign an edge between two vertices if the spheres assigned by these two vertices meet. In Chapter 1, we noted that the collimators do not deliver clear cut boundaries for spheres-there is some spillover. The neurosurgeons currently assume that the portion between two spheres gets enough dosage of radiation if the distance between the centers of the two spheres is less than or equal to eleven tenths of the sum of the radii of the two spheres. Thus for any two vertices assigned for two spheres satisfying this condition we assign an edge between them. Then we have the following proposition. Proposition 4.3.1 Let G — {V, E} be a graph for the sphere packing plan of a brain tumor. For any vertices Vi and Vj in V, d{ci,Cj) < f^(''i + Tj) if and only if {viiVj} G E. Thus we have the following edge set; E = {{i,3]\d{c^,Cj) < (ll/10)(r, + rj) where i < j, i = 1,2, ...,n- 1). Since any brain tumor is connected in this article, there is at least one (u, v)- path in G for every two vertices, u and v in G. Thus we have the following propo- sition. Proposition 4.3.2 The graph G = {V, E} produced by the above method for a given tumor is a connected graph. Since we are dealing with unlabeled graphs in this article, we have the following proposition. , 65 Proposition 4.3.3 For any sphere packing treatment plan for a given brain tumor, there exists a unique graph that we assign to the treatment plan. By means of the above method, we get a unique connected graph G = {V,E} for the sphere packing treatment plan for the tumor. This graph does not have the information about the positions of the dose spheres as an aspect of the structure and looks only at how the spheres are attached. It is clear that the graph G does not have a loop or multiple edges between two vertices, since every edge is assigned for two different vertices which are assigned for two attached spheres. 4.4 Order in the Vertex Set To get a maximal tree from a graph we may need to delete some edges in the graph. Thus we need to label each vertex in order to choose certain edges to delete, even though we are dealing with an unlabeled graph in this chapter. So there is no specific meaning for this labeling except that it is only used to choose a maximal tree for the graph. Example 4.4.1 Let P be the sphere packing treatment plan (see Figure 4-3) for a given brain tumor. Figure 4-3 Then, by Proposition 4.3.3, there is a unique graph G for the sphere packing plan. The graph is given below in Figure 4-4. Figure 4-4 66 There are two difTerent isomorphism classes, namely Ti and T2, of maximal trees for the graph G. That is, we could choose either of these for a maximal tree to assign the graph G. Since, in our algorithm, we want to get the same maximal tree for a given graph every time, we need certain rules to get the same tree. (See Figure 4-5.) Ti T2 Figure 4-5 In this chaper, the graph comes from a sphere packing treatment plan. That is, the main shape of the brain tumor depends on the size of spheres and the connection between spheres. Even though we cannot keep the information about the size of spheres in the graph, it seems to us that the bigger the sphere is, the more it has a chance to get attached to more spheres. So we assume that the larger degree vertices play a more important role in classifying the tumor shapes into trees than the smaller degree vertices. That is, by choosing a largest degree vertex first, the shape of the tumor is apparently most closely preserved. Thus, in the previous example, we choose the vertex q or s as the starting vertex; then we pick all the incident edges. Then we get the tree Ti . Therefore we want to choose the tree Ti for the maximal tree of G. Note that the tree T2 produces a linear graph which does not show the shape of the tumor as closely as Ti. But there are some vertices which are more important than the bigger degree vertices. Recall the graph G in Example 4.2.16. Then, in the block 6*2, it is clear that the vertex k has the largest degree, 5. But the cutvertices, 6 and c, play a critical role in obtaining a maximal tree of G. So, to get a maximal tree for a graph G, we want to start at the cutvertices of G first, instead of the vertices with the largest degree. So we want to label the cutvertices first. On the other hand, there 67 are difFerent kinds of 'cutvertices' in some graphs. The following example shows such a case. Example 4.4.2 Let G = {V, E} be the graph in Figure 4-6. Wg Un. ^10/ \u8 "11 • \ X "3 11 ^ ^ \ U2 U4 Figure 4-6 Then there are two cutvertices of the graph G, namely U2 and Uiq. Us- ing these two cutvertices, the graph G is separated into four subgraphs, namely Gi, G2, G3 and G4. (See Figure 4-7.) G^ Ull- U\Q Uio UlO - -' T = • , G3 «2 W2 Figure 4-7 Then the subgraphs Gi, G2, and G3 are blocks, but the subgraph G4 con- tains its own cutvertices, U4 and Us, which are not cutvertices of the graph G. We separate the subgraph G4 into four subgraphs by using its cutvertices U4 and ug. 68 (See Figure 4-8.) Note that there is no specific order in labeling the subgraphs. So at this moment, we relabel the subgraphs of G hy Hi, H2-, ■ ■ ■ , Hf. "a* .,: «4 U4 Figure 4-8 Then, again, the subgraphs i/i, H2, ■ ■ ■ , He are blocks, but the subgraph Hr contains its own cutvertex, uq, which is neither a cutvertex of the graph G nor a cutvertex of the subgraph G4. We separate this subgraph Hr into two subgraphs by using ue. (See Figure 4-9.) And we relabel the subgraphs of G by Bi, B2, ..., Bg. Therefore {^2,^^10} is the set of cutvertices of the graph G. But {^4,^8} is the set of the cutvertices of a subgraph which is produced after the first separation using the cutvertices of the graph, and ug is the cutvertex of a subgraph which is produced after the second separation. For the purpose of labeling the vertices in a graph, we separate these cutvertex sets for different levels, from each other. Definition 4.4.3 Let G be the graph assigned for a given sphere packing plan P. Then the vertex set V{G) of the graph G is the union of two disjoint subsets, namely Ci{G) and C'i{G), where Ci{G) = {v e V{G)\ v is a cutvertex of G} 69 and Ci^(G) = V{G) - Ci{G). We call Ci(G) the first step cutvertex set of G. For every i — 2,3, . . . , |V(G)|, we define a subset Ci{G) of Cf_i(G) as the collection of the vertices of C?_i(G), which are cutvertices of a subgraph produced after the (i — l)-th separation using the elements of Cj_i(G). Then we call C,(G) the i-th step cutvertex set of G, and let C^{G) = C-_^{G) — Ci{G). We assume that there are finitely many vertices in a given graph. If there exists at least one cutvertex, then there exists an integer 1 < fc < n such that Ci{G) ^ for every i < k, and Ci{G) = for every i > k + 1. Then we call k the separation step constant of the graph G, and let C%G) = {CkYiG). If there is no cutvertex of G then the graph is a block, and we say that the separation step constant of G is 0. U4 U4 Figure 4-9. Proposition 4.4.4 Let \V{G)\ = n and let the separation step constant of G be k > 0. Then there is a sequence of integers {mi, m2, . . . , ruk} with < mi < m2 < ...<mk such that |Ci(G)| = mi, and \Ci{G)\ = nii - m^_l, for i = 2,3, . . . ,k. 70 Proof Since A; > 0, the first step cutvertex set Ci{G) is not empty. Thus there is a positive integer, namely mi, such that |Ci(G)| = mi. For every i = 2,3, ...,A;, let rrii = mi_i + |C,(G')|. For every z = 2, 3, . . . , A;, the i-th step cutvertex set C,(G) is not empty. So we have that m{ > m,_i, and |C,(G)| = rrii — rrii-i. J_ Now we label the vertices as follows; (1) the vertices in Ci{G) are labeled by {1, 2, . . . ,mi}, (2) for every i = 2,3, . . . , A;, the vertices in Ci{G) are labeled by {mj_i + l,mj_i + 2, . . . ,mi — l,mi}, and (3) the vertices in C'^{G) are labeled by {ruk + 1, m^ + 2, . . . , n}. We arbitrarily name the vertices of C,(G) and C"'(G), and denote that Ci{G) = {ui,U2,. ..,Umi}, Ci{G) = {um,_i+i,iim._i+2,-- • ,w„j,} for ? = 2, 3, . . . , A), and C^IG) = {umi,+i-,Um^+2, ■ ■ ■ ,Un}. It is clear that for every vertex Up G Ci{G) and every vertex Ug G Cj{G) with i ^ j, we have that -p < q \{ and only if % < j. And also, for every vertex Up 6 Ci{G) for every z = 1,2, ...,A;, and every vertex Ug 6 C'^(G), we have that p < q. Assume that, for every vertex u,-, the center and the radius of the sphere which is assigned to that vertex Ui, are Cj = {x,-,y,, 2,} and r,-, respectively. We now relabel the elements for each of the sets, Ci(G), C2{G), ..., Ck{G) and C'^{G), in the following way: for every pair of vertices, Ui,Uj, in one of Ci{G),C2iG), . . . ,Ck{G) and C"=(G), i < j if and only if (i) d{ui) > d{uj); or (ii) If d{ui) = d{uj), then r,- > rf, or ' (ii) If d{ui) = d{uj) and r,- = r^, then Xi < Xj\ or (iii) If d{ui) = d{uj), Vi = r^, and a;,- = Xj, then j/, < y^; or (iv) If (/(u,) = d{uj), r, = Tj, a;, = Xj, and t/, = y^, then 2,- < z^-. Note that d{ui) represents degree of the vertex Ui in G. 71 It is clear that for any two different spheres, at least one of the coordinates is different. Thus any two distinct spheres can always be compared by the above order. Therefore the above order for the vertices of the graph is well defined. 4.5 Maximal Tree from a Graph In this section, we develop an algorithm that will uniquely select a maximal tree from the graph which is produced for a given brain tumor. The choice is made so that the tree will most closely resemble, in our opinion, the shape of the tumor - that is, of the graph obtained for the tumor. Let G = {V, E) be the graph for a given sphere packing plan. Let V{G) = {ui,U2, . . . , u„} for some positive integer n, where all the vertices in V are labeled by the method in the previous section. Define a subgraph To = {V{G),Fo) with ^(^0) = V ^ V{G) and Fq = 0; that is, there is no edge in Tq. Then, for every i = 1,2, ...,n, we have that Pjoi'^i) = i- (See Definition 4.2.4.) (1) For the vertex ui, let Fi = Fq U Ig{ui). (See Definition 4.2.11.) Let Ti = (!/((?), Fi). The subgraph (V(Fi),Fi) C Fi is a tree. Thus, if V{Fi) = V{G), then Fi = {V{G), Fi) = (V'(Fi), Fi) is our maximal tree of G. Note that for every vertex V eV{Fi) we have that Pti{v) = 1, and for every vertex Uj V{Fi), we have that Ptx{uj)=3. (2) Assume that V(Fi) 7^ V{G). For the vertex U2, there are two cases, that is, Pti{u2) = 1 and Fti(u2) = 2. Now define the edge subset Ig{u2) by /G(ii2) = Ig{u2) - {{U2,v} G E\ Pt,(v) = 1}. (a) If Ft, (■"2) = 1, that is, there is a (ui,W2)-path in the subgraph Fi, then let F2 = FiU/^(h2). Each edge in the set {{u2,v} e E\ Pr.iv) = 1} = {{u2,v} e E\v e V{Fi)} makes a cycle with {ui,U2} and {ui,v}, since Pt^M = 1. Thus there is no cycle in the subgraph (V(F2),F2), so it is a tree. Let F2 = {V{G),F2) C G. 72 If V{F2) = V{G), then T2 = iV{G),F2) = {V{F2),F2) is our maximal tree of G. Note that for every vertex v G ^(^2) we have that Pxiiv) = 1, and for every vertex II J ^V{F2) we have that PtjC^^j) = j- (b) If Pti{u2) — 2, then there is no (?ii,U2)-path in the subgraph Ti. (i) Ifthere is a non-empty subset {m2i, ^22, • • • , W2J C V(/g(^^2)) where Pt^{u2,) = 1 for « = 1, 2, . . . , i and 2, < 2^ for 1 < z < j < i!, then let F2 = FiD I'g{u2) U {{u2,U2,]]. Then the subgraph (V(F2),F2) C G is a tree. Let T2 = {V{G),F2) C G'. If y(F2) = V{G), then r2 = {V{G),F2) = {V{F2),F2) is our maximal tree of G. Note that for every vertex v € V{F2) we have that Pxiiv) - 1, and for every vertex u^ ^ ^^(^2) we have that Pr^iuj) = j- (ii) If none of the vertices in V{Ig{u2)) has p-value 1, that is, for every vertex V e V{Ig{u2)) there is no (ui,u)-path, then let F2 = FiU IgM- Since PtA^) = 1 for every vertex w E Fi and Pt,{v) = 2 for every vertex v G Ig{u2), the subgraph (V(F2),F2) is a forest, but not a tree. Let T2 = {V{G),F2) C G. It is clear that the subgraph T2 cannot be our maximal tree, even if we have that V{F2) = V{G), because the subgraph T2 is disconnected. Note that for every vertex v € ^(^2) = ViFi U IgM) = V{Fi) U V(/g(u2)) we have that Pt,{v) = 1 if y G V(Fi), and Pxiiv) = 2 if u 6 V{Ig{u2)). And, for every vertex Uj ^ V{F2), we have that PTiM =j. ■■■■■ ■ - - (3) By induction, at the j-th step, the subgraph T,_i = (y(G),F,_i) has been defined. We want to define the subgraph T, C G. For the vertex u^, there are two cases, that is, Pt^_,{uj) = j and Pt^_,{u^) = q for some 1 < q < j. For every 2 = 1, 2, . . . ,n, define m,_i(i) = mm{/e {1,2, ... ,n}\PT^_^{ui) = i ^ind m E Ag{u,) }. If the set {/ E {l,2,...,n}\ui € V{Ig{uj)) and Ft,_,(w/) = z } is empty, then the vertex Um^_^^i) is not defined. So there is no edge {uj,Um _,{{)}. 73 (a) Let /V,_, {uj) = i; that is, for every i = 1, 2, . . . , j — 1, j + 1, . . . , n, there is no (uj,Ui)-path in the subgraph Tj_i = (y(G),F,_i). Let f; = i^,_iu(ur=i{K,ti„^_,(,)}}). Then the subgraph {V{Fj),Fj) is a forest. Let T, = (y(G),F,) C G. If 1/(F_,) = V{G) and |V(f;)| = |F,| + 1, then, by Proposition 4.2.13, the subgraph Tj = {V{G), F,) = {V{Fj), Fj) is our maximal tree of G. (b) Let Ptj_^{uj) = q for some I < q < j, that is, there is a (u,,?ij)-path in the subgraph r;_i =(]/(G'),F_,_i). Now let F, - F,_i U (Uf^i, ,.^J {u„ii„^_,(,)} }) . Then the subgraph (y(F,),F,) is a forest. Let Tj = {V{G),Fj) C G. If V{Fj) = V{G) and \V{Fj)\ = \Fj\ + 1, then by Proposition 4.2.13, the subgraph Tj = (V(G'), Fj) = {V{Fj), Fj) is our maximal tree of G. Note that if u is an z'-th step cutvertex, then d{u) in G is same as d{u) in T,_i. Also note that, for every i = l,2,...,n, {ui, ua, . . . ,«,} C V(Fi), that is, V(G) = V(F„). We will see in Theorem 4.5.3 that 7; = (K(G),F„) = (y(F„),F„) is our maximal tree of G. By the Tree Classification Theorem (Theorem 3.6.8), this tree F„ can be denoted by a unique perfect sequence. Example 4.5.1 Let G = {V,E) be a graph where V = {wj, U2, . . . ,««}, which are ordered as in the previous subsection, and F = {ei, 62, . . . , 613} as in the figure below. Clearly, the graph G does not have a cutvertex, so the order is decided by only the sizes of the spheres and the coordinates of the centers of the spheres. "8 ei3 U7 62 Ui y.3' e-r/ /\ \eio \ \ei2 y / e& es y^b h\ \/ /e4 \ \/ /eii U2 eg ue Figure 4-10 74 Let To = {V{G), Fo) 1 oe a subgraph of J — (y,E) where Fq = 0, as shown in Figure 4-11. • tt7 • • U3» tl2 W4 • • «8 •^^5 Figure 4-11 Since IgM = {ei ,62}, let Fi = FoUlaiu 1) = {ei,e2}. Then V{Fi) = {ui,U5,U7}. Since n^i) = {U] ,^5, uj} ^ V{G), the t ree 1 V{Fi),Fi) is not a maximal tree of G. Let Ti = iV{G),F, which is shown in Figure 4-12. Us • U7_ 62 Ui «3. • tl4 • • •^5 .. "2 tt6 Figure 4-12 We have that mi(i) = i for i = 1,2,3,4,6, and 8, but mi (5) and mi(7) do not exist. Since Pti{u2) = 2 and AqM = {u3,U4,ue}, let i^2 =FiU(U=3,4,6{K,liJ}) '■ = i^l U /g(w2) = {ei, 62} U {63, 64, 65} = {ei, 62, 63, 64, 65). Then ^(Fs) = {uj, ug, 1*7,^2, W3, ^4,^6} / V^fC) and the subgraph (V(F2),F2) is a forest, not a tree. Thus it cannot be a maximal tree of G. Let T2 = {V{G),F2). (See Figure 4-13.) • I, ■ 1 yju '. <^-V^L . i H 75 Figure 4-13 Note that Pt,{ui) = Pt,M = Pt,{u,) = 1, Pt,{u2) = Pt.M = Pt.M = Pt2{u6) = 2, and Pr^ius) =8. Thus we have that m2(l) = l,m2(2) = 2, m2(8) = 8. Note that m^ii) does not exist for i = 3,4,5,6,7. Since ui ^ A{u3) and Pr^ius) - 2, weget /^3 = ^2U{{?i3, Ms}} = {61,62,63,64,65,67}. Since the subgraph (y(f'3),F3) is a forest, but not a tree, it is not a maximal tree of G. Define T3 = {V{G),F3). (See Figure 4-14.) U2 65 ue Figure 4-14 Note that PtA^i) = ^73(^5) = PnM = 1 and ^73(^2) = PtsM = Pni^d = Pn{u&) = Pr^ius) = 2. Thus we have that 7713(1) = 5 and 7713(2) = 4. Note that m3{i) does not exist for i = 3,4, ...,8. Since Pt-^^u^) = 2, we define F^ = F^iJ {{u4,U5}} = {61,62,63,64,65,67,68}. Since ViF^) = {vi,V2,. . . .v^] = V{G) and \V{F4)\ = 8 = IF4I + 1, the subgraph T = iV{F^), F4) is a maximal tree of G. (See Figure 4-15.) 76 r'Mi^4r^^.,r■: U2 65 ue Figure 4-15 At this moment, we have that Pt{ui) = Pjiu^) = . . . — Pt{us) = 1. Then, for every iit G V{G) with t > 4, we have that Ft = F4. Thus, for every t > 4, the subgraph {V{Ft),Ft) is same as T = (V(F4), F4). The next example shows how we get the maximal tree for a given graph containing some cut vertices. Example 4.5.2 Let G be the graph in Example 4.2.16. (See Figure 4-1.) Then Ci{G) = {6,c, e} and Q(G) = {a,d, f,g,h,i,j,kj,m,n}. In Ci{G), we have that d{e) = 5, d{b) = 4 and d{c) = 3. On the other hand, in C^iG), we have that d{k) = 5, d{m) = d{n) = 3, d{d) = d{f) = d{g) = d{h) = d{l) = 2, d[a) = d{i) = d{j) = 1. And C2 = 0. Thus we order the vertices as follows; vi = 6, V2 — b, V3 = c and V4 = k, {v5,ve} = {m,7i}, {^7,^8,^9,^10,^11} = {dj,g,hj}, {^12,^13,^14} = {a,ij}. Assume that V5 = m, vg = n, Vr = d, Vs = /, vg = g, v^ = h, Vn - /, Vx2 = a, Vi3 = i, ui4 = j, which are decided by the sizes and centers of the corresponding spheres. (See Figure 4-16.) VU V2 V3 V7 Figure 4-16 ^13 t^io Vi Vs Vu 77 Since Ig{vi) = { {^'1,^7}, {^'b^s}, {^1,^9}, {vi,t;io}, {^1,^^14} }, let Fi = Ig{vi). Then V(Fi) = {vuVj^vs^v^^vio^vi^}. Since V{Fi) # ^(G), the tree T^ = (V(G),Fi) is not a maximal tree of G. Thus, for the cut vertex vi, we have the following sub- graph which is Ti = {V{G),Fi). (See Figure 4-17.) V5> vn ^^13* Ve' V4 U12 V2 V3 V7 Figure 4-17 Since Pti{v2) = 2, and, for every vertex v € Ag{v2) = {^^3,^^4,t^6,t^i2}, ^ri(^^) 7^ 1, let F2 = Fi U Ig{v2). The subgraph (1/(^2), F2) is a forest, but not a tree. Thus it cannot be a maximal tree of G. Now, for the cutvertex V2, we have the following subgraph which is T2 = {V{G),F2). (See Figure 4-18.) V5' Vn t^l3' Figure 4-18 Since ^0(^3) = {t^2,i^4,^^7}, PtA^2) = PtA^a) = 2 = Pt^v^), and PtA^j) = 1, let F3 = F2 U {{vj^vj}]. Then, for the cutvertex U3, we have the following subgraph which is {V{F^),F^). Then the subgraph {V{F^),F^) is a tree. But V{F3)^V{G). 78 Thus it cannot be a maximal tree of G. We have the following subgraph which is T3 = {V{G), F3). (See Figure 4-19.) V5» vn Vl3» V12 V2 V3 Vj Figure 4-19 Since Ag{v4) = {v2,V3,V5,Ve,Vn}, ^nd Pn{v2) = PtAv^) = Pt,{v^) = 1 = Pn{v4),PTAv5) = 5,Pt,{vu) = 11, we define i^4 = F3 U {{1^4,^5}} U {{^4,^11}}- Then the subgraph {V{F4),F4) is a tree. But V{F4) ^ V{G). Thus it cannot be a maximal tree of G. Then, for the cutvertex V4, we have that the following subgraph which is T4 = {V{G),F4). (See Figure 4-20.) ;' ;^ v . ! • »,f = •^^R ^^13« W12 V2 V3 vr Figure 4-20 For the vertices V5,Ve,V7,V8,VQ, there is no 'new' edge. Thus we get the same sub- graph as above, that is, T4 = T5 = Te = T7 ^ Ts = Tg. But, for the cutver- tex vio, we have that V13 G V{Ig{vw)) and PtA^is) = 13 7^ 1 = Pt,{vio)- Thus 79 Fio — FqU { {^10,^13 } and ViFio) = V{G). Therefore we have the following sub- graph which is r = (y(G), Fio) = (V(Fio), Fio). (See Figure 4-21.) Ul2 V2 U3 V7 Figure 4-21 Ul4 Clearly, the subgraph T = {V{Fio), ^lo) does not include a cycle. Thus it is a max- imal tree of G. That is, for every t = 11,12,13,14, we have that {V{Ft),Ft) = iV{Fio),Fio). Therefore, the subgraph T = {V{Fio), Fw) = {V{G), Fw) is the max- imal tree of the graph G. For this resulting tree T = (V(i^io), Fio), choose a vertex sequence s by s = {vi,V7, V3, U2, V4, V5, ^11,^6, ^12, 'Wio, ^^13, ^8, ^9, Vu) ■ Then the sequence P = (5,1,1,3,2,0,0,0,0,1,0,0,0,0) is the degree sequence of s. By Theorem 3.4.12, P satisfies DSC. It is clear that P also satisfies DSbC. By Corollary 3.6.10, P is the perfect sequence for the tree T = iViFio),Fio). Theorem 4.5.3 Let G — {V, E} be a graph for a sphere packing plan where V = {ui,U2,...,Un} with the order described in Section 4-4- Let the subgraph (V(F„),F„) of G come from the above procedure. Then V(F„) = V{G). There- fore (V(F„), F„) is a maximal tree of G and there is a unique perfect n-sequence for the tree (y(F„),F„). Proof The subgraph (1/(F„),F„) is connected. In fact, assume that the sub- graph {V{Fn),Fn) contains two disjoint subtrees, namely Tj and T2. Then the '•{VtH 80 path-value for every vertex in Ti is diflferent from the path-value for every ver- tex in T2. Since the graph G is connected, there is at least one edge e € E{G) which connects the two subgraphs Ti and T2 and e ^ E{Ti U T2) = F„. Let { {vj^ ,Vk^}, {uj2, Vkj},- ■ ■, {vj^, Vkg} } be the collection of such edges where Vj^ G Ti and Ufc, € ^2 for i = 1,2,. . . ,q. Without loss of generality, let ji < ji for every i = 2, 3, . . . , <?. Then it is clear that {vj^ , uaii } G Fj^ by the procedure of getting the subgraph (y(i^„),F„). Then {vj^,Vk^} € i^„. This is a contradiction. Therefore the subgraph (y(F„),F„) is connected. The path-value in the procedure of getting the subgraph (V'(F„),F„) guarantees that the subgraph (V(F„),F„) is acyclic. There- fore {V{Fn), Fn) is a tree. It is clear that, for every i — 1,2, ... ,n, the vertex set V{Fi) contains the vertices Ui,U2,. . . ,Ui. Thus V[Fn) contains all the vertices of G, since V{Fn) D {ui,U2, . . . ,Un} = V{G). That is, V{Fn) = V = V{G). Hence the subgraph (y(F„),F„) is a maximal tree of G. By the Tree Classification The- orem (Theorem 3.6.8), it is clear that there is a perfect n-sequence for the tree (y(F„),F„). ± Definition 4.5.4 The tree shape of a brain tumor is the tree corresponding to that tumor, or equivalently, its unique corresponding perfect sequence. Definition 4.5.5 Two tumors have the same shape if and only if their corresponding graphs obtained from their respective sphere packing plans are the same. As in Chapter 2, for any brain tumor, we have a unique sphere packing plan which can be denoted by a graph. From the previous theorem, we have a unique perfect sequence for the graph. That is, we can assign exactly one perfect sequence to each brain tumor. So, if two perfect sequences are distinct, then their corresponding trees, and therefore their respective corresponding graphs and sphere packings, are also distinct. That is, if two tumors are represented by distinct perfect sequences, then their corresponding trees are not isomorphic. And their respective graphs and 81 sphere packing plans are not isomorphic. Thus, we may consider their shapes to be distinct. Therefore we have the following as our main theorem of this section. Theorem 4.5.6 The perfect sequences are invariants of the shapes of arbitrary brain tumors. 4.6 Graph from a Maximal Tree Let r = { V, £■'} be a maximal tree for a graph G = {V, E} which is obtained from the sphere packing plan of a given tumor or solid shape. We observe that we can recover the original graph, G, from T. Since V{T) = V = V{G) and E{T) = E' C E = E{G), we need to add the remaining edges to the edge set of the maximal tree to get the graph G. Since the graph G comes from the sphere packing treatment plan, each vertex w in G denotes a sphere of the sphere packing plan. Thus, for every vertex u,- 6 G, let c, = {xi,yi,Zi) and r^ be the center and the radius of the sphere. By Proposition 4.3.1, for any two vertices v, and Vj in V if d{ci,Cj) < ^{ri + rj), then the edge {vi,Vj} is in the edge set, E{G), of the graph G. Thus E'U{{vi,v,} eVxV\ d{c,,c,) < i^(r, + r,)} = E. Therefore we get the graph G = {V,E}. 4.7 Algorithm for Our Maximal Tree Let G = {V,E) be the graph for a sphere packing plan with \V\ — n. STEP A Find all the i-th step cutvertices of the graph G, for 1 < i < n. STEP B Label the vertices in the vertex set V by the order explained in Section 4.4. STEP C By induction, for each i = l,2,...,n, get the subgraph {V{Fi),Fi) of G. Then T = (V'(F„),F„) is our maximal tree. APPENDIX A SHELLING PROGRAM FOR SPHERE PACKING In this appendix, we provide the C++ program we developed to get the sphere packing plan for a given tumor shape. The first section shows the program translating the data from CT scan to the data of appropriate form for the main program, which is in the second section. Note that this program does not include the score function which was developed by Thomas Wagner. We refer the reader Appendix E for the complete article on the sphere packing treatment plan. A.l Program for Data Reading // rewrite data file into x,y,z format // & produce the total # of data, x,y,z min & max #include <iostream.h> #include <f stream. h> #include <iomanip.h> #include <stdlib.h> #include <math.h> mainO { const int nofdata=3370; // comes from data003.txt int xposit ion [nof data] , yposition[nofdata] , zposition[nofdata] ; int q; float a; float b; float c; int k=0; { ifstream inClientFileC'dataOOS.txt", ios::in); while (inClientFile >> a >> b » { xposition[k] = int (floor (a)) yposition[k] = int (f loor(b)) zposition[k] = int (floor (c)) k++; } . c) // check the number // check the number // check the number int xmin' int xmax^ int ymin^ int ymax: int zmin- int zmax: =xposition[0] =xposition[0] =yposition[0] =yposition[0] =zposition[0] =zposition[0] for (int i=0; i<nofdata; i++) { if ( xposition[i] < xmin ) xmin = xpositionEi] ; 82 83 else if ( xposition[i] > xmax ) xmax = xposition[i] ; else if ( yposition[i] < ymin ) ymin = yposition[i] ; else if ( yposition[i] > ymax ) ymax = yposition[i] ; else if ( zposition[i] < zmin ) zmin = zposition[i] ; else if ( zposition[i] > zmax ) zmax = zposition[i] ; setw(5) cout « nofdata << setw(5) << xmin << setw(5) << xmax << setw(5) << ymin << setw(5) << ymax << setw(5) << zmin << setw(5) << zmax; cin >> q; .-.- Program for Center Searching // searching the centers for pat 2 A. 2 #include <iostrecLm.h> #include <f stream. h> #include <iomanip.h> #include <stdlib.h> #include <math.h> crnoH ^i-^%x int square (int) ; int MAX (int, int, int ) ; mainO { const int nofdata=3370; const int xmin = -32; const int xmax = -4; const int ymin = -29; const int ymax = 4; const int zmin = -57; const int zmax = -37; const int xfix = 1-xmin; const int yfix = 1-ymin; const int zfix = 1-zmin; // function prototype // function prototype // check the number from mM003.txt // check the number // check the number // check the number // check the number // check the number // check the number int xposition [nofdata] , yposition [nofdata] , zposition [nofdata] ; int q; float a; float b; float c; int k=0; { ifstream inClientFile("data003.txt", ios::in); while (inClientFile » a » b » c) { xposition[k] = int (f loor(a))+xf ix; yposition[k] = int (f loor(b))+yf ix; zposition[k] = int(f loor(c))+zf ix; k++; } } const int x = xmax - xmin + 3; const int y = ymax - ymin + 3; const int z = zmax - zmin + 3; const int nc = x*y*z; // number of cells int cc[nc]; // status value for (int i=0; i<nc; ++i) ccCi] = -3; int xc[nc]; // x-coord. of c[nc] int yc[nc]; // y-coord. of c[nc] int zc[nc]; // z-coord. of c[nc] // setting the x,y, z-coord. for each cell for (int i=0; i<nc; i++) { zc[i] = floor(i/(y*x)); xc[i] = floor((i-zc[i]*y*x)/x) ; yc[i] = i-zc[i]*y*x-xc[i]*x; // setting the boundary of tumor by -1 for (int i=0; i<nofdata; i++) { cc[zposition[i]*x*y + xposition[i] *y + yposition[i]] = -1; // setting the initial of normal by cc[0] = 0; // setting the normal cell by int h=0; for (int j=0; j<x*y; j++) { for (int i=0; i<nc; i++) ■C if ( cc[i] == -3 ) { if (cc [i-1] ==0 I I cc [i+1] ==0 I I cc [i-y] ==0 I I cc [i+y] ==0) { cc[i] = 0; h++; } else; } else; } 85 if (h==o) ,. „.,:^..virr-v;.,: break; * •-•..-.. else ,.„ ,, . , ► ■ ■ ; \ h=o; l^lr--. -- ".' ^ } ^^■- r -:,' r:'/'.; i // setting the remaining tumor cell by -2 for (int i=0; i<nc; i++) // checking { if ( cc[i] == -3 ) // checking cc[i] = -2; // checking else; // checking } // checking // setting the boundary cells int maxrad; int nof maxrad; for (int j=0; j<=MAX(x,y,z)/2+l; j++) { int k=0; for (int i=0; i<nc; i++) { if (cc[i] == -1 II cc[i] == -2) { k++; if ( cc[i-l] == j II cc[i+l] ==j II cc[i-y]==j II cc[i+y]==j II cc[i-y*x]==j I I cc[i+y*x]==j ) { ccCi] = j + 1; nof maxrad = k; } else; > ... else; } maxrad = j ; if (k==0) ,.. ■ , break; ■ , - else; } // checking the no . of nof maxrad // if nof maxrad > 100, then you have change the number if (nofmaxrad >100) { cout « endl « endl « endl « endl « endl « « endl « endl « endl « endl; cin >> q; } else; // pick the boxes with maxrad int suprad[lOO] ; int TotalNofBox4[lOO] ; ■; int TotalNofMax=0; for (int i=0; i<nc; i++) { if (cc[i]==maxrad) 86 4 } { suprad[TotalMof Max]=i; TotalNofMax++; \ else; ' : • 5 cout « TotalNofMax « endl; cin >> q; // Count for the number of centers of each case for (int k=0; k<TotalNofMax; k++) { // reset TotalNofBox4[ ] to for (int i=0; i<100; i++) { TotalNofBox4[i] = 0; } TotalNof Box4 [maxrad] ++ ; int tcc[nc]; // temporary cell notion for (int i = 0; i<nc; ++i) tccCi] = cc[i]; // reassign tcc[i] for 'for' loop // remove the biggest sphere for (int p=0; p<nc; ++p) { int dist = floor(sqrt( square (yc[suprad[k]]-yc[p]) + square (xc [suprad [k] ] -xc[p] ) + square (zc [suprad [k]]-zc[p]) )); if ( dist < maxrad ) tcc[p] =0; else; > // setting the remaining tumor cell by -2 for (int i=0; i<nc; i++) { if ( tcc[i] >= 1 ) tcc[i] = -2; else; } // setting the boundary cells for (int j=0; j<=MAX(x,y,z)/2+l ; j++) { int 1=0; for (int i=0; i<nc; i++) { if (tcc[i] == -2) { if ( tcc[i-l] == j II tcc[i+l] ==j II tcc[i-y]==j II tcc[i+y]==j II tcc[i-y*x]==j || tcc[i+y*x]==j ) { tcc[i] = j + 1; ++1; > else; } ■ , else; > if (1==0) . ' break; 87 else; } // check if there is more maxrad pixcel for (int i=0; i<nc; i++) { if ( tcc[i] == maxrad ) • , . { cout « endl « endl << endl « " WARNING! ! ! WE HAVE MORE 'MAXRAD' PIXCEL AT (" « xc[i] « "," « yc[i] « "," « zc[i] « ")' « endl; cin >> q; break; } else; //remove the smaller or = sphere for (int j=maxrad-l; j>l; — j) { for (int i=0; i<nc; ++i) { if ( tcc[i] ==j ) { TotalNofBox4[j]++; // remove the sphere for (int 1=0; Knc; ++1) { int dist = floor(sqrt( square (yc [i] -yc[l]) + square (xc [i] -xc[l] ) + square (zc[i]-zc[l]) )); if ( dist < j ) tcc[l] = 0; else; } // setting the remaining tumor cell by -2 for (int i=0; Knc; i++) { if ( tcc[i] >= 1 ) tccCi] = -2; else; } // setting the boundary cells for (int j=0; j<=MAX(x,y,z)/2+l; j++) { int 1=0; for (int i=0; Knc; i++) { if (tcc[i] == -2) f { if ( tcc[i-l] == j I I tcc[i+l] ==j II tcc[i-y]==j II tcc[i+y]==j || , ,v tcc[i-y*x]==j II tcc[i+y*x]==j ) ' ■ { tcc[i] = j + 1; ++1; } else; > else; } if (1==0) break; } 88 else; } ■; } else; } } // output the result of centers { of stream outClientFile( "pat003-Nof Centers .txt", ios::app); { outClientFile « endl « endl « endl « endl « endl « (k+1) « setw(5) « "(" « (xc[suprad[k]]-xfix) « "," « (yc[suprad[k]]-yfix) « "," « (zc[suprad[k]]-zf ix) << ") with radius = " << maxrad << endl; } } for (int j=maxrad; j>l; j — ) { of streajn outClientFile("pat003-Nof Centers. txt" , ios::app); { outClientFile « setw(4) « j « setw(4) « TotalNofBox4[j] « endl; } } // Search for centers for (int k=0; k<TotalNofMax; k++) { int tcc[nc]; // temporary cell notion for (int i = 0; i<nc; ++i) tcc[i] = cc[i]; ^ // reassign tcc[i] for 'for' loop // output the result of centers { of stream outClientFile("pat003-centers. txt", ios::app); { outClientFile « (k+1) « endl « setw(5) « "x" « setw(5) « "y" « setw(5) « "z" « setw(lO) « "radius" « endl « setw(5) « (xc[suprad[k]]-xf ix) « setw(5) « (yc[suprad[k]]-yfix) << setw(5) << (zc[suprad[k]]-zfix) << setw(lO) << maxrad << endl; } } // remove the biggest sphere •' for (int p=0; p<nc; ++p) { int dist = floor(sqrt( square (yc[suprad[k]]-yc[p]) + square (xc[suprad[k]]-xc[p]) + square (zc[suprad[k]]-zc[p]) )); if ( dist < maxrad ) tcc[p] =0; else; } // setting the remaining tumor cell by -2 for (int i=0; i<nc; i++) { if ( tcc[i] >= 1 ) tccLi] = -2; 89 '• ■- ,.■- .*-- . ,'. '..-■ ;- Jv">X ^ ■■ , - ^ 1^.^^^^ else; } // setting the boundary cells for (int j=0; j<=MAX(x,y,z)/2+l; j++) { int 1=0; for (int i=0; i<nc; i++) ■C if (tcc[i] == -2) { if ( tcc[i-l] == j 1 1 tcc[i+l] ==j II tcc[i-y]==j II tcc[i+y]==j II tcc[i-y*x]==j I I tcc[i+y*x]==j ) { tcc[i] = j + 1; ++1; > else; } else; } if (1==0) break; else; } // check if there is more maxrad pixcel for (int i=0; i<nc; i++) { if ( tcc[i] == maxrad ) { cout << endl << endl << endl << " WARNING!!! WE HAVE MORE 'MAXRAD' PIXCEL AT (" « xc[i] « "," « yc[i] « "," « zc[i] « ")" « endl; cin >> q; break; } else; } ■ //remove the smaller nr- = funhf^r-f^ for (int j=maxrad-l; j>l; — j) { for (int i=0; i<nc; ++i) { if ( tcc[i] ==j ) . { TotalNofBox4[j]++; // output the result of centers { of stream outClientFile("pat003-centers .txt" , ios : :app) ; { outClientFile « setw(5) « (xc[i]-xfix) « setw(5) «(yc[i]-yfix) « setw(5) « (zc[i]-zfix) << setw(lO) << i << endl; } . } // remove the sphere for (int 1=0; Knc; ++1) { int dist = floor(sqrt( square (yc [i] -yc[l] ) + square (xc[i]-xc[l]) + square (zc[i]-zc[l]) )); if ( dist < j ) tcc[l] = 0; 90 else; } // setting the remaining tumor cell by -2 for (int i=0; i<nc; i++) { if ( tcc[i] >= 1 ) tcc[i] = -2; else; } * ^' .'.-., ■■> // setting the boundary cells for (int j=0; j<=MAX(x,y,z)/2+l ; 1++) { int 1=0; for (int i=0; i<nc; i++) { if (tcc[i] == -2) { if ( tcc[i-l] == j II tcc[i+l] ==j II tcc[i-y]==j II tcc[i+y]==j || tcc[i-y*x]==j II tcc[i+y*x]==j ) { tcc[i] = j + 1; ++1; } else; } else; } if (1==0) break; else; } } else; } > { of stream outClientFile("pat003-centers.txt", ios::app); { outClientFile « endl ; } } } } - - int square (int a) { return a*a; } int MAX(int a, int b, int c) { int p=0; p = a; if (a<=b) P = b; else if (a<=c) p = c; else; return p; ■ • '•-,.--■ , » < i \ ■•■ .■ > > I APPENDIX B PROGRAM FOR THE MAXIMAL TREE OF A GRAPH In this appendix, we provide the Mathematica program we developed in joint work with Matthew Harvey. The program below was written by Matthew Harvey to get the maximal tree for the graph which we assigned for a brain tumor. Note that this program does not use the method of ordering for the vertices as in Chapter 3. Instead this program uses some commands which are in the function package in the Mathematica program library. If anyone wants to develop a program like this using a different program language, we recommand the vertex ordering algorithm in Chapter 3. << DiscreteMath'Combinatorica' Off [General: : spell] LexPrecedes[a_, b_] := Module [{i}, For[i =1, i <= Min [Length [a] , Length [b] ] , i++, If[ a[[i]] != b[[i]], If[ a[[i]] > b[[i]], Return [True] , Return[False] ] ] ]; If[ Length [b] > Length [a]. Return [False] ]; Return [True]] DegreePoint[a_, k_] := Count [Flatten [ToUnorderedPairs [a]] , k] ; IndSubgraph [Graph [g_, v_] , s.List] := Module [{i, j, newmat , sc}, newmat = g; sc = Complement [Range [Length [v]] , s] ; For[i = 1, i <= Length [g], i++, For[j = 1, j <= Length [g], j++, If [MemberQ[sc, i] || MemberQ[sc, j] , newmat[[i, j]] = 0]]]; Graph [newmat , v] ] ; ■ CutPoints[gr_] := Select [ArticulationVertices [gr] , DegreePoint [gr, #] > 2 &] NonCutPartitions[gr_] := Module [{partitions, cpts, bees, skeleton}, partitions = {}; bees = Select [BieonnectedComponents [gr] , Length [#] > 2 &] ; partitions = Union [partitions, bees] ; skeleton = IndSubgraph [gr , Union [ Complement [ Range [V[gr]] , Flatten [bees] ], 91 ■ ] ]; 92 CutPointsCgr] partitions = Union [partitions , Select [ConnectedComponents [ FromllnorderedPairs [ Select [ToUnorderedPairs [ skeleton] , # != Intersection[#, Flatten [ Select [BiconnectedComponents [skeleton] , Length [#] > 2 &] ] ] &] ] ], Length [#] > 1 &] ]; Table [ Select [ ToUnorderedPairs [gr] , # == Intersection[ #, partitions [[i]] ] &] , {i, Length[partitions]}]] '♦<->«; U'^ V. :^ ^ . , "■■■■■' ' ''>\A\ APPENDIX C PROGRAM FOR CLASSIFYING TREES BY SEQUENCES In the first section, we provide the Mathematica program we developed in joint work with Matthew Harvey. This program was written by Matthew Harvey to get the maximal degree sequences for any given integer n > 2. And we show the program results up to n = 10 in the second section. C.l Program Off [General: : spell] << DiscreteMath'Combinatorica' DoPartitions[n_] := Module [{i, k, templist, returnlist}, If [n == 0, {{}}, returnlist = {}; ForCk = n, k >= 1, k— , templist = DoPartitionsEn - k] ; For[i = 1, i <= Dimensions [templist] [[1]] , i++, returnlist = Append [returnlist , Flatten[{k, templist [[i]]}] ] ] returnlist h i Filter [thelist_] := '•■'■■ -'- ^ .:./"• t '■ Select [thelist , ! ( Memberq[{l, 2}, #1[[1]]] I I (Max[#l] != First[#l]) I I (Count [#1, Max[#l]] > 1) ) ft] AddZerosToSeq[part_] := Module [{nZeros, n, i, j, k, sum, positions, seqs, withzeros}, If [Length [part] == 1, Return [{Table [If [i == 1, part[[l]], 0], {i, part[[l]] + 1}]}] Ir seqs = {}; sum = Sum [part [ [i] ] , {i, 1, Length [part] }] ; nZeros = (sum + 1) - Length [part] ; n = Table [k, {k, 3, sum}]; . . positions = KSubsets[n, nZeros -1]; 93 94 ] For[i = 1 , i <= Length [positions] , i++, k = 2; withzeros = {First [part] }; For[j = 2, j <= sum, j++, If [MemberQ [positions [[i]] , j] , withzeros = Append [withzeros, 0] , withzeros = Append [withzeros, part[[k]]]; k++ ] ]; withzeros = Append [withzeros, 0]; seqs = Append [seqs, withzeros] seqs AddZeros [seq_] := Flatten[Table[ AddZerosToSeq[seq[[i]]], {i, 1, Length [seq]} ], 1] SubSeqs [dseq_] := Module [ {branchlist, branch, workseq, branches, i}, branches = dseq[[l]] ; workseq = Drop[dseq, 1]; branchlist = {}; For[i =1, i <= branches, i++, dsum = workseq[[l]] ; workseq = Drop [workseq, 1]; branch = {dsum}; While [dsum != 0, dsum += (workseq [[1]] - 1); branch = Append [ branch, workseq [[1]] ]; workseq = Drop [workseq, 1] branchlist = Append [branchlist , branch] branchlist ] LexPrecedes[a_, b_] := - - Module [{i}, For[i = 1, i <= Min [Length [a] , Length [b]], i++, If[a[[i]] != b[[i]], If[ a[[i]] > b[[i]], Return [True] , Return[False] ] ]; If [Length [b] > Length [a]. Return [False] ] ; Return [True] ] WeightsQ[dseq_] := Module [{i, subseqs, flag}, subseqs = SubSeqs [dseq] ; flag =1; If [OrderedQ [subseqs, LexPrecedes] , 95 For[i =1, i <= Length [subseqs] , i++, If[ ! Weightsq [subseqs [[i]]] , flag=0, flag*=l ] Return [False] ]; If[ flag == 1, Return [True] , Return [False] ] ] DegreeSumQ[dseq_] := Module [{dsum}, dsum = dseq[[l]] ; For[i =2, i <= Length [dseq] , i++, dsum += dseq[[i]] - 1; If [dsum == 0, If[i == Length [dseq] , Return [True] , Return [False] ] ] ]; Return [False] ] ExtractSubtree[dseq_] := Module [{rtotal} , rtotal = dseq[[l]] ; i = 1; While [rtotal > 0,i++; rtotal += dseq[[i]] - 1; ]; Take [dseq, i] RewriteTree[dseq_, i_] := Module [{branchesoff, subtree, brlength, seqlst}, If[i == 1, Return [dseq] ] ; branchesoff = i - 1; While [ ( branchesoff > 1 && Sum [dseq [[k]] - 1, {k, branchesoff, i - 1}] < ) I I dseq[[branchesoff]] == 0, branchesoff — ]; brlength = Length [ ExtractSubtree [Drop [dseq, i - 1]] ] ; subtree = Drop [dseq, {i, i + brlength - 1}]; subtree [ [branchesoff] ] — ; seqlst = SubSeqs [Take [dseq, {i, i + brlength - 1}]]; seqlst = Append [seqlst, RewriteTree[subtree,branchesoff]] ; seqlst = Sort [seqlst, LexPrecedes [#1 , #2] &] ; Flatten [{dseq[[i]] + 1, seqlst}] RightOrderQ[dseq_] := Module [{pos, seqs, j, rewritten}, pos = Flatten[ Position[dseq, dseq[[l]] - 1] ] ; If [pos == {}, Return [True] ] ; seqs = {}; For[j = 1, j <= Length [pos], j++, rewritten = RewriteTree[ dseq, pos[[j]] ]; 96 If [LexPrecedes [rewritten, dseq] && rewritten != dseq, Return [False] ] -\l '\ 1 ' :>»•,.; '-,4 n ]; Return[True] "lit-Ai N'T .. ? ] "* ) . LemmasQ[dseq_] := . - -^ , DegreeSumQ[dseq] && WeightsQ [dseq] && RightOrderq[dseq] CheckLemmas [1 st seq_] : = Module [{retseq, twoseq, i, j, n, p}, retseq = {}; J = 0; P = 10; n = Length [Istseq] ; For[i = 1, i <= n, i++, If [ j > n/10, Print [p, '"/."]; P += 10; j = ]; If[LenmiasQ[ lstseq[[i]] ], retseq = Append[ retseq, lstseq[[i]] ] ]; twoseq = {2}; If [Length [Istseq] > 0, For[i = 2, i < Length [ retseq [[1]] ] - 1, i++, twoseq = Append [twoseq, 1] ]; twoseq = Join[twoseq, {0, 0}]; retseq = Append [retseq, twoseq] ; retseq DSTRecursive[dseq_, bvert_, hvert_ , trparam. ] := Module [{i, v, tree, tempseq}, V = hvert ; tree = trparam; If [dseq != {0}, tempseq = Drop[dseq, 1]; For[i = 1, i <= dseq[[l]], i++, V++; tree = Append [tree, {bvert , v}] ; subseq = ExtractSubtree [tempseq] ; tempseq = Drop[tempseq, Length [subseq] ] ; {tree, v} = DSTRecursive [subseq, v, v, tree]; J > ]; {tree, v} 97 DegreeSeqToTree[dseq_] := First [ DSTRecursiveidseq, 1, 1, {}] ]; ToGraphics[ckd_] := For[t = 1, t <= Length [ckd], t++, Print [ckd[[t]]]; ShowGraph [Radial Embedding [FromUnorderedPairs [ DegreeSeqToTree[ckd[[t]]] ] ] 3 3 C.2 Some Program Results The notation for a degree sequence is {di,d2, . . . ,dn) . But the Mathematica program produces the sequence notation with { and }. So in this section, any set notation is actually denotes the degree sequence. Note that an n-tree has n vertices, so there are n-1 edges. n=3 {2, 0, 0> total n=4 {3, 0, 0, 0}, total : 2 {2, 1, 0, 0} n=5 total : 3 ■ '^ "■' " ' _ ' :'* {4, 0, 0, 0, 0}, {3, 1, 0, 0, 0}, {2, 1, 1. 0, 0} 98 n=6 total {5, 0, 0, 0, 0, 0}, {4, 1, 0, 0, 0, 0}, {3, 2, 0, 0, 0, 0}, {3, 1, 0, 1, 0, 0}, {3, 1, 1. 0, 0, 0}, {2, 1, 1, 1, 0, 0} n=7 total 11 {6, 0, 0, 0, 0, 0, 0}, {5, 1, 0, 0, 0, 0, O}, {4, 2, 0, 0, 0, 0, 0}, {4. 1, 0, 1, 0, 0, 0}. {4, 1, 1, 0, 0, 0, 0}, {3, 2, 1, 0, 0, 0, 0}, {3, 1, 2, 0, 0, 0, 0}, {3, 1, 0, 1, 0, 1, 0}, {3, 1, 1, 0, 1, 0, 0}, {3, 1, 1, 1, 0, 0, 0}, {2, 1, 1, 1, 1, 0, 0} fn'^ORJV \CP i</H- f jt^h.\ Vt if I 99 n=8 ■C7, 0. 0, {5, 2, 0, {5, 1, 1, {4, 2, 0, {4, 1, 2, {4. 1, 1, {3, 2, 2, {3, 2, 1, {3, 1, 2, 1 {3, 1, 1, ■C3, 1, 1, 1 {2, 1, 1, 1 , 0, 0, , 0, 0, , 0, 0. 0. 0. 0, 0, 0, 0, 0, 1, 1, total : 23 0, 0}, {6, 1, 0, 0, 0, 0, 0}, {5, 1, 0, 1, 0, 0, 0}. {4, 3, 0, 0, 0, 0, 0}, {4, 2, 1, 0, 0, 0, 0}, {4, 1, 0, 1, 0, 0, 0}, {4, 1, 1, 1, 0, 0, 0}, {3, 2, 1, 0, 0, 0, 0}, {3, 2, 1, 1, 0. 0, 0}. {3, 1, 1, 2, 0, 1, 0}, {3, 1, 1, 0, 1, 0, 0}, {3, 1, 1, 1, 1, 0, 0} 0, 0, 0}, 0, 0, 0}, 0, 0, 0}, 0, 0, 0}, 1. 0, 0}, 0, 0, 0}, 1, 0, 0}, 0, 0, 0}, 0, 0, 0}, 1, 0, 0}, 0. 0, 0}, 100 n=9 total : 47 {8 {6 {6 {5 {5 {5 {4 {4 {4 {4 {4 {4 {4 {4 {4 {3 {3 {3 {3 {3 {3 {3 {3 {2 , , , , . , , 0, 0} , il , 1 , , , , , , 0. , 2 , , , , , , 0, 0} , {6 , 1 , , 1 . . , , 0. , 1 , 1 , , , , , 0, 0} , {5 , 3 , , , , , , 0. , 2 , , , 1 , , , 0, 0} , {5 2 , 1 , , , , , 0, , 1 , 2 , , , , . 0, 0} . {5 1 , , 1 , , 1 , . 0, , 1 , 1 , , 1 . , , 0, 0} , {5 1 , 1 , 1 , , , , 0, , 3 , 1 , , . , , 0, 0} {4 2 , , , 2 , , 0. , 2 , 2 , , , , , 0, 0} {4 2 , , , 1 , , 1 0. , 2 1 , 1 . . 0. 0} {4 2 1 > , 1 , 0, , 2 1 1 , , , 0, 0} {4 2 1 1 > , 0, . 1 3 0, 0} {4 1 2 1 0. , 1 2 0, 0} {4 1 1 2 0, , 1 1 1, 0} {4 1 1 1 1 0, . 1 1 1 1 0, 0} {4 1 1 1 1 0, , 1 1 1 0, 0} {3 2 2 1 0. , 2 2 0, 0} {3, 2 1 2 0, 0. , 2 1 1 1 0. 0}, {3, 2 1 1 1, 0, . 2 1 1 0, 0}, {3, 2 1 1 1 0, 0, , 1. 2, 1 0, 0}, {3, 2 1 0, 1 0, 0. , 1. 2, 1, 0, 0, 0, 0}, {3, 1, 2 1, 0, 0, , 1, 1, 2, 0: 0, 0, 0}, {3, 1, 0, 1, 1, 0, 1, , 1, 1, 0, 1, 0, 1, 0}, {3, 1, 1, 0, 1, 1, 0, , 1, 1, 1, 0, 1, 0, 0}, {3, 1, 1, 1, 1, 0, 0, . 1, 1, 1, 1, 1, 0, 0} 0}. 0}. 0}. o>, 0}, 0}, 0}. 0}. 0}. 0}, 0}. 0}. 0}, 0}, 0}, 0}, 0}, 0}, 0}. 0}. 0}, 0}, 0}, n = 10 total : 106 {9, 0, 0. 0. 0, 0, 0, 0, 0, 0}, {8, 1. 0, 0, 0, 0, 0, 0, 0, 0}, {7. 2, 0, 0, 0, 0, 0, 0, 0, 0}. {7, 1, 0, 1, 0, 0, 0, 0, 0, 0}. {7, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {6. 3, 0, 0, 0. 0, 0, 0, 0, o>, {6, 2, 0, 0, 1, 0. 0, 0. 0, o>. {6. 2, 1. 0, 0. 0. 0. 0, 0, 0}. {6, 1. 2. 0, 0, 0, 0, 0, 0, 0}, {6. 1. 0, 1. 0, 1, 0. 0, 0, 0}, {6, 1, 1, 0, 1, 0. 0, 0, 0, 0}, {6, 1. 1, 1, 0, 0. 0, 0, 0, 0}, ■C5. 4, 0, 0, 0, 0, 0. 0, 0. o>. {5, 3, 0, 0, 0, 1, 0. 0, 0, 0}. {5, 3. 1. 0. 0, 0, 0. 0, 0, 0}. {5, 2. 0, 0, 2, 0. 0, 0, 0, 0}, {5, 2, 2, 0, 0, 0, 0. 0, 0. 0}. {5. 2, 0, 0, 1. 0, 1, 0, 0, 0}, {5, 2, 0. 0, 1, 1, 0, 0, 0. 0}, {5, 2. 1, 0. 0, 1, 0, 0, 0, 0}. {5, 2, 1, 0, 1, 0, 0. 0, 0, 0}. {5, 2, 1, 1, 0, 0, 0, 0, 0, 0}. {5, -'- > 3, 0, 0, 0, 0, 0, 0, 0}, {5. 1, 2, 0, 0, 1, 0, 0, 0, o>. {5, ■^ > 2, 1, 0, 0. 0, 0, 0, 0}, {5, 1, 1, 2, 0. 0, 0, 0, 0, o>, {5, -^ » 0. 1, 0, 1, 0, 1, 0, 0}. {5. 1, 1, 0. 1, 0, 1, 0, 0, o>. {5, -'- > 1, 0, 1, 1, 0. 0. 0. 0}, {5, 1, 1, 1, 0, 1. 0. 0, 0, 0}, ■C5. ■'- > 1, 1, 1, 0, 0, 0, 0. 0}, {4. 3, 2, 0, 0, 0, 0, 0. 0, 0}. {4, 3, 1, 0, 0, 0. 1. 0. 0. 0}. {4, 3, 1, 0, 1, 0, 0, 0, 0, 0}, {4, 3. 1. 1, 0, 0, 0, 0, 0, 0}, {4, 2. 3, 0, 0. 0, 0, 0, 0, 0}, {4, 2, 0, 0, 2, 0, 0. 1, 0, o>. {4, 2, 2, 0, 0, 0, 1. 0, 0, 0}, {4, 2, 2. 0, 0, 1, 0. 0, 0, 0}, {4, 2, 2, 1, 0, 0, 0, 0, 0, 0}. {4, 2, 0, 0, 1, 2, 0, 0, 0, 0}. {4, 2, 1, 0, 0. 2, 0, 0, 0, 0}, {4. 2. 1, 2. 0, 0, 0, 0, 0, 0}, {4, 2, 0, 0. 1, 0, 1, 0, 1, 0}, {4, 2, 0, 0, 1, 1, 0. 1. 0, o>. {4. 2, 0, 0, 1. 1, 1, 0, 0. 0}, 101 {4 {4 {4 {4 {4 {4 {4 {4 {4 {4 {4 {4 {3 {3 {3 {3 {3 {3 {3 {3 {3 {3 ■C3 {3 {3 {3 {3 {3 {3 {3 , 2 , 1 , , , 1 . , 1 , 0, , 2 , 1 , , 1 , , 1 , , 0, , 2 , 1 , , 1 , , 0, , 3 , , , 0, , 2 , , 1 , 1 0, , 2 , , , 1 0, , 2 , 1 . , 0, , 1 , , , 1 0, , 1 , 2 , , 0, , 1 , 1 , 1 , 1 0. , 1 , , 1 , 1 0, , 1 , 1 , 1 , 0, ', 2 2 , , , 0, , 2 2 , , , 1 0, , 2 2 . , 1 , 0, , 2 1 2 1 0, , 2 1 2 1 0, , 2 1 1 1 1, , 2 1 1 1 1 0, , 2 1 1 1 1 0, , 2 1 1 1 1 0. 2 1 2 0, 2 1 1 1 0. 2 1 1 1 0, 1 2 1 1 0, 1 1 2 1 0, 1 1 1 0, 1 1. 1 1 1 1, 1, 0, y ^ i 1. 1 1 1, 1 = 0, f -^ i 1. 1 = 1, 1, 1, 0, 0. 0}. 0}. 0}. 0}. 0}, 0}, 0}, 0}, 0}, 0}, 0}, 0}, 0}, 0}. 0}. 0}. 0}. 0}, 0}, 0}, 0}. 0}, 0}, 0}, 0}, 0}, o>. 0}. 0}. 0}. {4 {4 {4 {4 {4 {4 {4 {4 {4 {4 {4 {3 {3 {3 {3 {3 {3 {3 {3 {3 {3 {3 {3 {3 {3 {3 {3 {3 {3 {2 , 2 , 1 , , , 1 1 , , 0. , 2 , 1 , 1 , , , 1 , . 0, , 2 , 1 , 1 , 1 , , , , 0, . 2 , 2 , , , , 0, , 2 , , , 1 , 1 , , 0, , 2 , 1 . , 1 , , 0, , 3 . , , , , 0. , 2 , 1 , , , 0, , , 1 1 , , 1, , 1 , 1 , 1 , 0, , 1 , 1 1 , . 0, ', 2 ', 2 , , 2 , , 0, , 2 , 2 , , 1 1 , . 0, , 2 2 , 1 1 , . 0, , 2 2 , 1 1 , , 0, , 2 1 2 1 0, , 2 1 1 2 0. , 2 1 1 1 1, , 2 1 1 1 1 0, , 2 1 1 1 1 0, , 2 1 1 1 1 0, 2 1 1 1 0. 2 1 1 1 0, y ■*■ 1 2 1 1 0, y -*■ 1 2 1 1 0, J -'■ 1 1 1 2 0, » ^ 1 1 0, 1, 1 1, y ■*■ 1 1 1, 1 1. y ^ 1 1 1, 1, 1, 0, y -'• i 1, 1 = 1, 1, 1. 1> 0, 0}, 0}, 0}. 0}. 0}, 0}, 0}, 0}. 0}, o>, 0}, 0}, 0}, 0}, 0}, 0}, 0}, 0}, 0}, 0}, 0}, 0}, o>. 0}. 0}, 0}, 0}, 0}. 0}. 0} -end of data- APPENDIX D LABELED GRAPHS AND TREES D.l Number of Labeled Graphs and Labeled Trees To obtain the number of labeled graphs with n vertices, we need only observe that each of the (2) possible edges is either present or absent. Thus we have the following theorem: Theorem D.1.1 [5] The number of graphs on n labeled vertices is 2^^K In Lovasz [6], the Priifer-code is used to denote a labeled tree. And, for any given Priifer-code, one can construct the tree which is denoted by that code. Then, using the properties of the Priifer-code, Cayley proved the following theorem: Theorem D.l. 2 (Cayley) [8] The number of trees on n labeled vertices is n"~^. D.2 Sketch of the Construction of a Priifer-code Among the end vertices of a given labeled tree, pick the one whose label is minimal. Cut it off from the tree and write down the label of its adjacent vertex. Repeat this process until only one edge remain. At this point we have a sequence of n — 1 numbers written down. We call this resulting sequence the Priifer-code of the tree. The following example shows how we construct the Priifer-code of a given tree. Example D.2.1 Let T be the tree shown below. -3,6 Figure D-1. . ' '■ * ' • -^ There are 5 end vertices, 2, 3, 4, 6, 8. We cut off the smallest labeled end vertex which is 2. Then the sequence is (1) and the remaining tree is Figure D-2 below. Then we cut off the next smallest labeled end vertex which is 3, and add the label, 1, of the adjacent vertex of 3 to the sequence. That is, the sequence is (1, 1) . From the remaining tree we cut off the next smallest labeled end vertex which is 4. Then the sequence is (1,1,1). And we get the tree shape in Figure D-3. 102 V"^ 103 ".if.. * .-. • 3 *' ,6 Figure D-2. f6 15 7 8 . , ^ Figure D-3. Among the 3 end vertices, 1 is the smallest labeled one. So we cut off the vertex 1 and write down the label, 5, of the adjacent vertex of 1. The sequence then will be (1, 1, 1,5) and the remaining tree is Figure D-4. • 6 5 7 8 Figure D-4. The remaining tree has two end vertices, that is, it is a linear shape. We cut off the smaller labeled vertex, 6. And the sequence will be (1, 1, 1, 5, 5) . After we cut off the next smaller labeled vertex which is 5, and get the sequence (1, 1, 1, 5, 5, 7) , the remaining tree has only two vertices. It's clear we have to cut off the smaller labeled vertex which is 7 and the adjacent vertex will be 8. Therefore we do not need to add this number to the sequence. Hence the last sequence, (1, 1,1,5, 5, 7) , is the Priifer-code of the given tree T. If we assign different labels for the tree above, then we will get a different Priifer-code. But the code must consist of 6 terms which is two less than the total number of vertices in the tree. And each term can be any number among 1, 2, . . . , 8. Thus we have the following theorem. D.3 Reconstruction of a Tree from a Priifer-code Let (ai,a2,...,a„_2) be a Priifer-code. That is, we expect an n-tree. Let bi,b2,. . . ,bn-i be the indices of the removed points. Then, for any ?, 6, is obviously different from 61,62, ... ,6,_i,ai. Also, 6, / a^ if j > i, because 6, is removed in the i-th step, so it can not be an adjacent vertex later. Conversely, if A; ^ {6i, 62, . . . , 6._i, a„ a,+i, . . . , a„_2}, then Vk is an end ver- tex of V{T)-{vk,,Vk,,...,vt,_,}. Thus 104 bi - mm{k\k ^ {61,62, ... ,6i_i, ai,a,.,.i, .. . ,0^-2}- Let the sequence (1,1,1,5,5,7) be a Prufer-code. That is, ai = 1,02 = 1,03 = 1,04 := 5, as = 5,06 = 7. Then 61 = imn{k\k ^ {01,02, ••• ,06}} = min{/i;|A; {1,5,7}} = min{2,3,4,6,8} = 2. That is, there is an edge between oi = 1 and 61 = 2. Then 62 = min{A;|A; ^ {61,02, ... ,06}} = min{fc|A; ^ {2,1,5,7}} = min{3,4,6,8} = 3. Thus the tree T has an edge between 02 = 1 and 62 = 3. In a similar manner, we have the following: 63 = min{A;|/c ^ {61,62,03, ...,06}} = min{A;|^- ^ {2, 3, 1, 5, 7}} = min{4, 6, 8} = 4, (Thus T has an edge {03,63} = {1,4}) 64 = min{/i;|A; ^ {61,62,63,04,05,05}} = min{A;|A; ^ {2,3,4,5,7}} = min{l, 6,8} = 1, * (Thus T has an edge {04,64} =: {5,1}) 65 = min{A;|A: ^ {61,62,63,64,05,06}} = min{A;|A; ^ {2, 3, 4, 1, 5, 7}} = min{6, 8} = 6, (Thus T has an edge {05,65} = {5,6}) 65 = min{A;|A; ^ {61,62,63,64,65,06}} = min{A;|A; {2, 3, 4, 6, 7}} = min{5, 8} = 5, (Thus T has an edge {05,66} — {7,5}). And, for the vertex 05 = 7, the largest labeled vertex vs will be the remaining adjacent vertex, that is, there is an edge {7,8}. So the tree T has the vertex set V = {1,2,3,4,5,6,7,8} and the edge set £ = {{1, 2}, {1, 3}, {1,4}, {1,5}, {5, 6}, {5, 7}, {7, 8}}, which is the tree shape in the example above. That is, we can construct a labeled tree from a Priifer-code. Clearly, different Priifer-codes produce different labeled trees. BIOGRAPHICAL SKETCH Tae-Il Yi was born December 16, 1962 in Seoul, Korea. He attended the Dankook University from 1981 to 1988, earning a Bachelor of Science degree in math- ematics education in February 1988. During college, he was in the service of the Korean Army for 27 months. After college, he entered graduate school at Dankook University in March 1988, and completed a Master of Science degree in mathemat- ics in Feburary 1990. During that time he worked at Yongmoon High School as a mathematics teacher. He married Moon-Sil Kim on June 27, 1987. Their first son, Han-Yong (David), was born April 12, 1988, and their second son, Chang- Yong (Peter), was born May 3, 1994. In August 1991 Tae-Il Yi entered graduate school in the Mathematics De- partment at the University of Illinois at Urbana/Champaign. After receiving the degree of Master of Science in August 1994, he moved to graduate school in the In- struction and Curriculum Department of the College of Education at the University of Florida, and in August 1995 transfered to the University of Florida, Mathematics Department. He pursued a concurent degree in the College of Education and received a degree of Master of Education in December 1997. During his doctoral work in the Mathematics Department, he served as a graduate teaching assistant. He received a Russell Corporation Endowed Dissertation Scholarship Spring 2000. He is a member of the Phi Kappa Phi honor society. 105 I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. Beverly L.-^rechner, Chairman Professor of Mathematics I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. 'hilip Boyland Associate Professor of Mathematics I certify that I have read this study and that in niy opinion it conforms to acceptable standards of scholarly presentation and is ffillif adequate, in scope and quality, as a dissertation for the degree of Doctor of Phi^o^ophj^ JLames E. Kefeling / "^rofessor of Mathematic^ I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. lev, Li-Chien Shen Professor of Mathematics I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. Mary G. Kanxowski Professor of Teaching and Learning This dissertation was submitted to the Graduate Faculty of the Department of Mathematics in the College of Liberal Arts and Sciences and to the Graduate School and was accepted as partial fulfillment of the requirements for the degree of Doctor of Philosophy. August 2000 Dean, Graduate School UNIVERSITY OF FLORIDA 3 1262 08555 1710